2
$\begingroup$

I have proved the decision version of my problem be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just to compare the obtained minimum (or maximum) with target value in decision version. Thus, the decision version can be solved in poly-time as well. Since the decision version is $\mathcal{NP}$-hard, so is the optimization version, i.e., the optimization version is $\mathcal{NP}$-hard.

My question is how to prove the converse direction: if the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?

$\endgroup$
2
$\begingroup$

You can make a polynomial number of calls to your solver for the NP-complete problem to find the optimal solution. E.g., for the travelling salesman problem you would perform a binary search with a series of queries asking whether there is a tour with some cost $c$, gradually adjusting $c$ and bracketing the solution space until you have the optimal solution.

$\endgroup$
  • $\begingroup$ Just knowing what the cost of the optimal solution is, doesn't necessarily tell you what that solution is. There are many optimization problems where you can also reconstruct the optimal solution bit for bit by asking a series of slightly varying questions, though. $\endgroup$ – hmakholm left over Monica Jul 2 '19 at 0:04
  • $\begingroup$ As far as I know, all NP-complete problems are downward self-reducible so you should be able to extract the solution once you know that it exists, again with another polynomially bounded series of calls to the solver. $\endgroup$ – Kyle Jones Jul 2 '19 at 0:07
  • $\begingroup$ x @Kyle: Hmm you're right. If all else fails you can reduce to SAT and extract a certificate bit by bit. At least if we consider it implicit in the term "optimization problem" that it's as easy to check a solution as to find it, the solution itself can be that certificate. $\endgroup$ – hmakholm left over Monica Jul 2 '19 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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