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?

I in advance thank you for any suggestions!

  • $\begingroup$ Consider the decision version of TSP: given a graph and a value k, decide whether the shortest TSP tour has length at most k. One could try a binary search on k. $\endgroup$ – Rafael Castro Jul 1 '19 at 1:22
  • $\begingroup$ But what if the shortest length is not k, how many operations should we call to find the shortest length? Will it be poly-time operations? $\endgroup$ – Wei Jul 1 '19 at 1:30
  • $\begingroup$ You could start k with a big upper bound: the sum of the weight of all edges, as example. I guess any binary search on that space search should be polynomial. But this is just a guess. $\endgroup$ – Rafael Castro Jul 1 '19 at 1:40
  • $\begingroup$ I think it should be found in poly-time, since we have assumed P=NP, which implies a new upper bound can always be found in poly-time. But, I don't know how to convince myself for such conjecture. I want to show this guess theoretically. Anyway, thanks so much for replying. $\endgroup$ – Wei Jul 1 '19 at 1:44
  • $\begingroup$ The two words “binary search” are surely convincing enough? Rafael: You get a much smaller bound by just taking a random tour. $\endgroup$ – gnasher729 Nov 28 '19 at 10:31

If the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?

This depends on how technically precise you want to be.

The most correct answer is "No". Consider an optimisation problem $OP$ for which the encoded length of the output is superpolynomial in the encoded length of the input. Clearly no algorithm can produce the output in time polynomial in the encoded length of the input, so $OP \not\in \mathcal{P}$. However, the decision version $DP$ takes as input both the input of $OP$ and the guessed answer, so it is allowed time polynomial in the sum of the two, and in particular does not need to execute in time polynomial in the length of the problem per se.

However, if you're guaranteed that the output of $OP$ has (asymtoptically) an encoded length which is polynomial in the encoded length of the input (say $O(n^a)$ for input length $n$ and unknown $a$), then you can do a binary search, starting at any reasonable guess, doubling unless you get high enough, and then searching back down. The number of calls of the decision problem is $O(n^a)$, each call of the decision problem takes time polynomial in $n$, and the product of two polynomials is a polynomial.

| cite | improve this answer | |
  • $\begingroup$ In my problem, my question is given P=NP, I want to show finding the minimum (here is cost) in OP is poly-time. I can find the lower bound for cost. As for the upper bound, it is also exactly an value but have to be found trying exponential times. So, in such case, can I still find the minimum cost by binary searching in poly-time? $\endgroup$ – Wei Jul 1 '19 at 15:04

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.