2
$\begingroup$

Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not in NP-complete? Or would this just shows the availability of a polynomial algorithm for each NP problem indirectly?

Edit: I know that when NP-complete problems have polynomial algorithms, all NP problems must have polynomial algorithms. The question I am asking is that whether we can use the discovered algorithm for NP-complete to all NP problems just by modifying the algorithm. Or would we just know that NP problems must have a polynomial algorithm indirectly?

  • 0
    cross-posted to http://cs.stackexchange.com/questions/2653/np-completeness-and-np-problems2012-07-09

2 Answers 2

3

A problem $X$ is "NP-complete" if for any problem $Y$ in NP, there is a polynomial-time reduction from $Y$ to $X$. So if there is a polynomial-time algorithm for some NP-complete decision problem $X$, then there is a related algorithm for any problem $Y$ in NP, namely, reduce the instance of $Y$ to an instance of $X$ and use the polynomial-time algorithm for $X$.

2

Since NP-complete is a subset of NP, the answer to both of your questions is "yes". Suppose you had a deterministic poly-time solution to some NP-complete problem $D$. Then, by the definition of NP-completeness, every problem in NP could be poly-time reduced to $D$ and so would be in P. Since any NP-complete problem is by definition an NP problem, you would then have poly-time deterministic solutions to every NP problem, including those that are NP-complete. (Not to mention that you could then write your own meal ticket.)

  • 0
    I think this would even imply, that a NP-hard problem with polynomial solution must be NP-complete.2015-12-27