ADDITIONAL NP PROBLEMS: The following problems have a polynomial-time solution, but an exponential-time solution on a deterministic machine. There are literally hundreds of additional examples.
NP-COMPLETE PROBLEMS: All 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,
(a) There exists a polynomial-time algorith to restate a problem of type X as a problem of type Y, and
(b) 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 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.