3

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

Perry Bleiberg
  • 1,277
  • 8
  • 16
  • 3
    The claim you mentioned is true for $NP$-complete-problems, and even in this case, the existence of a polynomial algorithm for another problem would not imply that it would be easy to construct a polynomial algorithm for another problem. – Peter Jan 26 '16 at 16:29
  • @Peter: You are right about requiring $NP$-completeness, but I think you are wrong about what it would imply: it would be easy to construct a polynomial-time algorithm for any problem in $NP$. – TonyK Jan 26 '16 at 16:52
  • Probably a duplicate of this question. – TonyK Jan 26 '16 at 16:55
  • the idea is that a polynomial algorithm for SAT would make any problem in NP easy to solve in polynomial time. NP-complete is just another word for "which is able to represent any SAT problem" – reuns Jan 26 '16 at 17:14
  • @user1952009: SAT is just another NP-complete problem. Historically it was the first, but I don't think that there's anything else special about it. And NP-complete is not "just another word"! That's like saying General Relativity is just another word for gravity. – TonyK Jan 26 '16 at 18:11
  • @TonyK : a good teacher would explain the NP-complete concept as I did. solvable by a non deterministic Turing machine and SAT problem being highly related concepts. – reuns Jan 26 '16 at 18:19
  • @user1952009: "a good teacher...": well, that's about as persuasive as saying "my opinion is correct"! In my opinion (which is correct, by the way), your explanation doesn't convey any useful information at all. – TonyK Jan 26 '16 at 18:33
  • https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem that's the starting point of all this P/NP/complete/hard theory, right ? – reuns Jan 26 '16 at 18:36
  • @user1952009: The problem is, your "able to represent" is meaningless. How does one problem "represent" another? Even if you take all the jargon as given, you still need to say something like "reducible in polynomial time". And even then, NP-complete doesn't just mean "reducible to SAT in polynomial time". GR is not just another word for gravity! – TonyK Jan 26 '16 at 19:14

1 Answers1

6

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.

hmakholm left over Monica
  • 286,031