0
$\begingroup$

I have proved the decision version of my problem to be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just 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!

Improve this question
$\endgroup$
6
  • $\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, 2019 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$
    – Good to learn everything
    Jul 1, 2019 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, 2019 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$
    – Good to learn everything
    Jul 1, 2019 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, 2019 at 10:31

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$
    – Good to learn everything
    Jul 1, 2019 at 15:04
  • $\begingroup$ Did you read the answer? It fails if you have an optimisation problem where the size of the optimal solution is not polynomial in the size of the input. For example “given a set S, find a subset of the powerset of S that is in some way optimal”. If S has a million elements, the solution could be a set with close to 2^1,000,000 elements. But the last paragraph answers your question. $\endgroup$
    – gnasher729
    Dec 18, 2021 at 11:24

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.