[Overview] [Previous] [Next]

NP-Complete Problems

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,

• There exists a polynomial-time algorithm to restate a problem of type X as a problem of type Y, and
• There exists a polynomial-time algorithm to translate a solution to a type Y problem back into a solution for the type X problem.

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).