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? 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
 A: 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.
