1
$\begingroup$

Q: Suppose a language A is NP-complete. Is this following statement correct?:

A: If there is a polynomial algorithm to solve A, then it can be used to all the problems in NP.

My (and some others) first thoughts were that this answer is correct. But if you look at the following picture you can see that there exist problems which are only! NP. So let's take such a problem which is not NP-complete but NP. Thus a polynomial algorithm which can be used to solve any problem which is NP-complete can not be used to solve this problem which is only! NP. Is this correct?

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ NP-complete problems are the "hardest" problems in NP. If you can solve them you can solve all other problems in NP. This is how you should understand this figure - the level of difficulty increases vertically. $\endgroup$ – Yuval Filmus Aug 30 '17 at 9:05
2
$\begingroup$

Check the definition of NP-complete: a problem is NP-complete if it is in NP and every problem in NP reduces to it. So, if you have a polynomial-time algorithm for any NP-complete problem, you have a polynomial-time algorithm for every problem in NP. First, do the reduction; second, solve the complete problem.

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