If someone finds a polynomial time algorithm for a problem in NP, will we be able to construct polynomial time algorithms for all problems in NP?

Question

The existence of a polynomial time algorithm for a single problem in NP implies the existence of polynomial time algorithms for all problems in NP (correct me if I'm misunderstanding this). Suppose someone finds a polynomial time algorithm. Will we automatically be able to construct polynomial time algorithms for all problems in NP? Does it depend on the algorithm we discover, or other factors? Thanks

Answer 1

You're misunderstanding that. The problems of testing whether a number is even or ignoring the input and printing "false" are both in NP, and perfectly good polynomial-time algorithms are known for them.

On the other hand, a polynomial-time algorithm for an NP-complete problem would (automatically and systematically) lead to polynomial-time algorithms for every NP problem -- that's what "complete" means.

More precisely, what it means for a problem $P_1$ to be NP-complete is that

• $P_1$ is in NP, and
• for every other NP problem $P_2$ there is a computable function $f$ such that $f$ can be computed in polynomial time and for every possible input $x$, the answer of $P_2$ on $x$ is the same as the answer of $P_1$ on $f(x)$.

Thus if we find a polynomial-time algorithm for $P_1$, we can construct a polynomial-time algorithm for $P_2$ simply by combining our new $P_1$ solver with the $f$ that transforms $P_2$ instances into $P_1$ instances.

In order to do this, of course we have to know what $f$ is, not just that it exists. But the only known ways to prove that $P_1$ is NP-complete in the first place involve decribing concretely how to construct $f$ for any $P_2$, given a (sufficiently explicit) proof that $P_2$ is in NP.