Cook's Theorem

From Computers and Intractability: A Guide to the Theory of NP-Completeness , Garey and Johnson, W. H. Freeman Press, 1979

First, he emphasized the significance of "polynomial time reducibility," that is, reductions for which the required transformations can be executed by a polynomial algorithm. If we have a polynomial time reduction from one problem to another, this ensures that any polynomial time algorithm for the second problem can be converted into a corresponding polynomial time algorithm for the first problem.

Second, he focused attention on the class NP of decision problems that can be solved in polynomial time by a nondeterministic computer. (A decision problem is one whose solution is either "yes" or "no".) Most of the apparently intractable problems encountered in practice, when phrased as decision problems, belong to this class.

Third, he proved that one particular problem in NP, called the "satisfiability" problem, has the property that every other problem in NP can be polynomially reduced to it. If the satisfiability problem can be solved with a polynomial time algorithm, then so can every problem in NP, and if any problem in NP is intractable, then the satisfiability problem also must be intractable. Thus, in a sense, the satisfiability problem is the "hardest" problem in NP.

Finally, Cook suggested that other problems in NP might share with the satisfiability problem this property of being the "hardest" member of NP. He showed this to be the case for the problem, "Does a given graph G contain a complete subgraph of a given number k of vertices?"

Since then a wide variety of other problems have been proven equivalent in difficulty to these "hardest" problems in NP and the equivalence class has been given the name NP-complete problems.

Hence we are provided with a means of combining many individual complexity questions into one, "Are the NP-complete problems intractable?"

Reminder: A problem is intractable if there is no polynomial time algorithm that can possibly solve it.

All the provably intractable problems known to date fall into two categories:

undecidable
"nondeterministically" intractable

However, most of the apparently intractable problems encountered in practice today are decidable and can be solved in polynomial time with the aid of a nondeterministic computer. Thus, none of the proof techniques developed so far is powerful enough to verify the apparent intractability of these problems.

The question of whether or not the NP-complete problems are intractable is now considered to be one of the foremost open questions of contemporary mathematics and computer science.

As a matter of convenience, the theory of NP-completeness is designed to be applied only to decision problems.

1) Cook S.A. "The Complexity of Theorem Proving Procedures", Proc. 3rd Ann. ACM Symp on Theory of Computing, Association for Computing Machinery, New York, 151-158.