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

Copyright © 1996 by David Matuszek

Last modified Apr 23, 1996