17
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ In fact, a similar reasoning can be applied when we use $\frac{df}{dx}=0$ to find the place where a real-valued differentiable function $f$ can take its maximum value on a closed interval. If we know the function cannot take the maximum value at the ends of the interval, then it must be take the maximum value at one of places where $\frac{df}{dx}=0$. That is, indeed, a marvelous way to find maximum values of many such functions (discovered by Isaac Newton ? and Gottfried Wilhelm Leibniz ?). $\endgroup$
    – John L.
    Jan 27, 2020 at 8:36
  • 5
    $\begingroup$ Note that, in isolation, "the solution I have cannot be improved" [locally] might be because it is a local optimum (i.e., not necessarily global). $\endgroup$
    – Pablo H
    Jan 27, 2020 at 14:54
  • $\begingroup$ Am I missing something? Doesn't this prove that it's optimal, not that it's correct? $\endgroup$
    – Barmar
    Jan 27, 2020 at 16:21
  • 1
    $\begingroup$ If you had not shown the existence of an optimal solution, you'd be in the "$1$ us the biggest natural number because all other natural numbers can be improved by squaring"-siuation. But with existence shown ... $\endgroup$
    – Hagen von Eitzen
    Jan 28, 2020 at 0:02
  • $\begingroup$ It looks to me that the OP thinks that the other solutions might surpass the current optimal one, since the optimal solution cannot be improve and the other solutions are improvable, I don't know what's going on here but why not use the optimal solution for now while improving the other potential solutions that can surpass the current one in terms of optimization. $\endgroup$
    – Shiz
    Jan 28, 2020 at 6:55

3 Answers 3

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ I don't feel confident about this, as I am really not much of a logician, but when you say "The implication is just simple logic", isn't that true in classical logic but not in intuitionistic logic? My reasoning is that the proof uses double negation elimination: the optimal solution is not not provided by the algorithm, therefore it is provided by the algorithm? If the OP's method is indeed a classical proof, but not a constructive proof perhaps it could be worth mentioning. $\endgroup$
    – integrator
    Jan 27, 2020 at 9:47
  • 2
    $\begingroup$ @eru-cs I was trying to write in a level that is suitable for the questioner. I would like to keep that principle. Basically, you are raising the possibility that the solution could be in a state other than being optimal or being not optimal. Although I would concede that exceptionally rare possibility, I had assumed the questioner was in a situation where if a solution is not not optimal, then it is optimal. Had the situation been otherwise that exceptionally rare, the questioner should have raised some red flags, intentionally or unintentionally. Or so I believed. $\endgroup$
    – John L.
    Jan 27, 2020 at 10:57
  • 1
    $\begingroup$ @Vasting, when I wrote "a new and unorthodox way", it was meant for you. It could probably be just another mundane way for many experienced users here. As my comment indicates, people have been using that way for hundreds of years at least. $\endgroup$
    – John L.
    Jan 27, 2020 at 11:11
  • $\begingroup$ Proving that the algorithm finds any solution at all is already a big step and is implicitly mentioned here in the answer, but I haven't found that in the question. Please don't forget to prove that your algorithm finds a solution at all. $\endgroup$
    – kutschkem
    Jan 27, 2020 at 13:43
  • 2
    $\begingroup$ @eru-cs Even in intuitionistic logic, this is a valid proof that the given algorithm is optimal, because of the structure of terminating algorithms. We know an optimal solution exists, call it $O$, and let the new algorithm be $A$. On any given input $x$, we presume that $O(x)$ and $A(x)$ terminate with results in some discrete countable set of answers. Therefore $O(x)=A(x)$ or $O(x)\ne A(x)$. In the second case, $O\ne A$ so by the exchange argument $O$ can be improved, which is impossible. Thus $O(x)=A(x)$ for all $x$, so $O=A$. $\endgroup$
    – Mario Carneiro
    Jan 28, 2020 at 0:03
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.