NP-completeness and NP problems

Problem Detail: 

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?

Asked By : Zat Mack

Answered By : Juho

Recall a few definitions. A language $L \subseteq \{0,1\}^*$ is polynomial-time reducible to a language $L' \subseteq \{0,1\}^*$, often denoted as $L \leq_p L'$, if there is a polynomial-time computable function $f : \{0,1\}^* \to \{0,1\}^*$ such that for every $x \in \{0,1\}^*$, $x \in L$ iff $f(x) \in L'$. Now, $L'$ is $\text{NP}$-hard if $L \leq_p L'$ for every $L \in \text{NP}$. $L'$ is $\text{NP}$-complete if $L'$ is $\text{NP}$-hard and $L' \in \text{NP}$.

It is easy to see that if $L$ is $\text{NP}$-hard and $L \in \text{P}$, then $\text{P} = \text{NP}$. Likewise, if $L$ is $\text{NP}$-complete, then $L \in \text{P}$ iff $\text{P} = \text{NP}$. The intuitive reason is that if $f$ and $g$ are functions that grow at most as $n^c$ and $n^d$ respectively, then the composition $f(g(n))$ grows at most $n^{cd}$, which is also polynomial.

Assume you found a polynomial-time algorithm $A$ for a $\text{NP}$-complete problem $X$. Now, you could in polynomial time transform another $\text{NP}$-complete problem to $X$ and solve it using $A$. This is why we often say that it suffices to study whether any $\text{NP}$-complete problem can be decided in polynomial time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2653