NP-completeness and NP problems

Question

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?

Answer 1

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.

Answer 2

Here is one direct example:

The whole notion of NP-completeness came about when Cook and Levin and others discovered that it was possible to express the existence of an accepting path of computation in a non-deterministic Turing machine in a fairly straightforward manner as a Boolean expression as long as the length of the computation could be bounded.

So all of NP was reduced to the satisfiability of a certain Boolean expression that could easily be constructed from a hypothetical non-deterministic Turing machine whose running time could be bounded in a polynomial in the size of the input.

But the problem of the satisfiability of a Boolean expression is trivially in NP itself: simply assign all the variables non-determistically, evaluate the expression, and accept if it is true. There will be an accepting path of computation if and only if the expression is satisfiable. Therefore Boolean satisfiability is said to be NP-complete.

Likewise, for all existing problems known to be NP-complete, there is an explicit reduction that could be applied to solve any problem in NP in deterministic polynomical time if a suitable algorithm were found for that problem.

But the possibility of finding a polynomial algorithm for a problem known only indirectly to be NP-complete (without an explicit reduction) has not been ruled out, and this would be the case for any non-constructive proof that P=NP, since if P=NP then all problems in P are trivially NP-complete.