# What does the search problem imply about the decision problem?

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?

• 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$? – Yuval Filmus Dec 2 '19 at 21:59
• 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. – mymemesarespiciest Dec 2 '19 at 22:07

## 1 Answer

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.