Stephen A. Cook: The Complexity of Theorem-Proving Procedures
A short while ago, I noticed that Cook's theorem is only available for download in the 1971 typewriter version, hardly readable and with some typing errors. So, I decided to transliterate Cook's famous paper "The Complexity of Theorem-Proving Procedures" into TEX format.
In 1971, this paper was a major breakthrough in computational complexity theory, and no computer scientist or mathematician who is interested in theoretical computer science gets around Cook's proof that the boolean satisfiability problem (SAT) is NP-complete. This formulation is modern; in Cook's parlance, it reads
If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies},
followed by the theorem that SAT can be reduced to 3SAT, expressed in
The following sets are P-reducible to each other in pairs (and hence each has the same polynomial degree of difficulty): {tautologies}, {DNF tautologies}, D3, {subgraph pairs}.
In short, he proves these claims by constructing maps from boolean formulas to Turing machines. If you want to learn more, read the paper!
My transliteration is available in DIN A4 and Letter format. If you find any errors, please contact me!
Download
| DIN A4 format: |  Cook1971_A4.pdf |
111 KB |
| Letter format: | Cook1971_Letter.pdf |
111 KB |
last modified: 10 Feb 2009