Can I use the following method to prove an algorithm is correct?

Question

I'm trying to show that a solution I have obtained via an algorithm is correct. The way I plan on doing this is first by showing that an optimal solution does indeed exist. Then, I plan on showing that every other solution that is not the solution provided by my algorithm cannot be optimal. Finally, I show that the solution I have cannot be improved in the same way as any other solution.

Is this enough to show that my algorithm is optimal? In this case I am avoiding doing an "exchange argument" a la greedy algorithms. In fact, I don't really prove anything about how my solution is an improvement of the other ones, but simply that all of the other ones can be improved, and given that an optimal solution exists, the one I have must be it because it cannot be improved in the same way that the other ones can.

Answer 1

I am rather surprised that you raised this question since the meticulous and enlightening answers you have written to some math questions demonstrate sufficiently that you are capable of rigorous logical deduction. It seems that you became somewhat uncomfortable when you stumbled upon a new and unorthodox way to prove an algorithm is correct.

Believe in yourself. Believe in logic.

Yes, I believe you have shown your algorithm is correct. To be absolutely clear, suppose you have shown all of the following.

• An optimal solution exists.
• Your algorithm provides a solution and only one solution.
• Every solution that is not the solution provided by your algorithm cannot be optimal.

Then your algorithm must provide an optimal solution. The implication is just simple logic.

You do not even need to show that solution provided cannot be improved in the same way as any other solution.

Answer 2

You have: There is an optimal solution, and any solution not found by your algorithm is non-optimal. It follows that the optimal solution is found by your algorithm, so the third part is not needed.

For problems with two or more optimal solutions you won’t be able to show the second part unless your algorithm finds all optimal solutions.

Answer 3

but simply that all of the other ones can be improved, and given that an optimal solution exists, the one I have must be it because it cannot be improved in the same way that the other ones can.

It does seem that there's something slightly to patch up here. Do you have a proof that this procedure for making an improvement always makes an improvement when one is available? If you have such a proof, then simply showing that the procedure makes no improvement to your solution is enough to qualify the solution as optimal, and the only reason to even refer to other solutions is to show that yours is a unique optimum.

If you don't have such a proof, then you need to prove that your solution is actually optimal and not just a point where your "improvement procedure" fails to make progress. I think your intuition is correct that if every other solution can be improved, then the one that can't is an optimum, but it may fall short of a really rigorous proof without an appeal to something like the contraction mapping theorem.

In particular, if you could show that your "improvement procedure"

1. Never actually produces a worse solution, and
2. Always produces a solution that is nearer by some metric to your chosen solution than the one it was given as input

then you would be showing that your solution is a fixed-point of the improvement procedure and that every sequence leading to it is monotone, which should prove, using monotone convergence, that your solution is optimal.