New answers tagged


Work in somewhat that direction is superoptimization, take a short stretch of machine instructions and search for a shorter/faster one doing the same. The hard part is to check that they really have the same effect. It is a very expensive process, even for it's extremely narrow objective.


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 ...


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.


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 ...

Top 50 recent answers are included