[Overview] [Previous] [Next]
All of the known NP problems have a remarkable characteristic: they are all reducible to one another. What this means is that, given any two NP problems X and Y,
This is what the "complete" refers to when we talk about NP-complete problems.
What this means is that, if anyone ever discovers a polynomial-time algorithm for any of these problems, then there is an easily-derived polynomial-time algorithm for all of them. This leads to the famous question:
Does P = NP?
No one has ever found a deterministic polynomial-time algorithm for any of these problems (or the hundreds of others like them). However, no one has ever succeeded in proving that no deterministic polynomial-time algorithm exists, either. The status for some years now is this: most computer scientists don't think a polynomial-time algorithm can exist, but no one knows for sure. This was a hot research topic for a while, but interest has died down on the problem, for the simple reason that no one has made any progress (in either direction).
Copyright © 1996 by David Matuszek
Last modified Apr 23, 1996