Is the following statement correct?
If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
We don't know that $\mathrm{P}\neq\mathrm{NP}$ so we don't know that the decision problem itself can't be solved in polynomial time!
But, under the assumption that $\mathrm{P}\neq\mathrm{NP}$, the optimization version of an $\mathrm{NP}$-complete problem can't be solved in polynomial time. If we could, for example, compute the shortest travelling salesman tour in polynomial time, we could certainly tell in polynomial time whether there's a tour of length at most $d$
answered Feb 10, 2017 at 14:05