-1
$\begingroup$

Let $\Pi_{dec}$ be an NP-complete decision problem and let $\Pi_{opt}$ be its corresponding optimization problem. Assume $\Pi_{opt}$ can be solved in polynomial time.

  1. What does this imply for $\Pi_{desc}$?
  2. What does this imply for the class of NP-complete problems and the class NP, respectively.

I am not sure of my answers. For #1, I said that this does not imply anything. For #2, I don't really have any idea. Why would it say anything about NP problems?

$\endgroup$
  • $\begingroup$ Suppose you find a maximum cut in a graph. Does it help you to solve MAX CUT, which asks whether the value of the maximum cut is at least $k$? $\endgroup$ – Yuval Filmus Dec 2 '19 at 21:59
  • $\begingroup$ You could check if the max cut is at least $k$. But, my understanding is that search $\leq_p$ decision. Which means you can claim that if decision can be solved in polynomial time, then so can the optimization problem. Not the other way around. $\endgroup$ – mymemesarespiciest Dec 2 '19 at 22:07
1
$\begingroup$

Let us take as an example MAX CUT.

The optimization problem is: given a graph $G$, find the value of the maximum cut.

The decision problem is: given a graph $G$ and an integer $k$, determine whether there is a cut of value at least $k$.

If we can solve the optimization problem, then we can solve the decision problem: just compare the value of the maximum cut to $k$.

Conversely, if we can solve the decision problem, we can solve the optimization problem, using binary search.

$\endgroup$

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.