3
$\begingroup$

I find this quote here on page 13

Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p time solvable?

This is very unbelievable to me since NP complete problems are so different in nature and comes in a variety of form such as longest path, dominating vertex, halting problem, knapsack problem. Can someone show me how this statement is true?

$\endgroup$
3
$\begingroup$

This statement means exactly what you have said: if any NP-complete problem is solvable in polynomial time, then all of them are. This follows from the definitions: a problem X is NP-complete if all problems in NP are polynomial time reducible to it, that is, if for any problem Y in NP there is a polynomial time function $f_Y$ such that for all $w$, $w \in Y$ iff $f_Y(w) \in X$. Now suppose that you could solve X in polynomial time using some algorithm A. For any NP problem Y, you can use $f_Y$ in conjunction with A to solve Y in polynomial time.

This is indeed surprising, and it is one reason why most researchers conjecture that NP is different from P: otherwise all these disparate problems will have polynomial time solutions.

$\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.