[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,

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