This question already has an answer here:

Is the following statement correct?

If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.


marked as duplicate by Yuval Filmus complexity-theory Feb 10 '17 at 14:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


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$


Not the answer you're looking for? Browse other questions tagged or ask your own question.