Cook's theorem

The Canadian scientist Stephen A. Cook founded a new class of problems in complexity theory in 1971 . He showed that there is a subset of the class NP to which all problems from NP can be reduced . This subset is representative of the difficulty of NP and is referred to as NPC complete ( NPC for English NP complete ). The eponymous set of Cook states that the satisfiability of propositional logic ( SAT , v. Engl. Satisfiability ) is NP-complete. Leonid Levin published a comparable sentence independently of Cook in 1973, which is why one sometimes also speaks of the Cook and Levin theorem .

With a well-known representative of the class, the proof for other problems from NP was much easier to carry out, since for a problem M from NP it was sufficient to construct a polynomial reduction from SAT to M in order to prove the NP-completeness of M. In 1972 Richard M. Karp expanded NPC by 21 further problems in this way, several hundred have been identified to date.

Evidence sketch

Let be any language in NP . A reduction from to SAT is now to be constructed, i.e. H. a description of how a propositional formula can be calculated from a character string in polynomial time, which can be fulfilled if and only if . Because lies in NP, there is a nondeterministic Turing machine that decides in polynomial time whether belongs to the language . The basic idea of ​​the reduction is now to express the statement that the calculation of the machine when inputting that belongs to the language in a propositional formula. This formula must contain a description of the machine , a description of the input and the rules according to which a nondeterministic Turing machine works. ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle x}$ ${\displaystyle x\in L}$ ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle L}$ ${\displaystyle M}$ ${\displaystyle x}$

To do this, we use these three families of Boolean variables, each with the following interpretation:

• ${\displaystyle Q[t,q]}$: The Turing machine is currently in the state and no other. ${\displaystyle t}$ ${\displaystyle q}$
• ${\displaystyle H[t,z]}$: The read head of the Turing machine is at the time on the belt cell and no other. ${\displaystyle t}$ ${\displaystyle z}$
• ${\displaystyle S[t,z,a]}$: At the time, there is the symbol in the belt cell of the Turing machine and nothing else. ${\displaystyle t}$ ${\displaystyle z}$ ${\displaystyle a}$

Only those tape cells that the read head actually reaches are of importance. Since a Turing machine can only move the reading head by one tape cell in one computing step, the number of computing steps also limits the number of tape cells that can be reached.

The formula now consists of the following clauses :

1. At the beginning there are the symbols of in the band cells , surrounded by spaces. ${\displaystyle x}$
2. At the beginning is in the starting state. ${\displaystyle M}$
3. ${\displaystyle M}$maintains its state transition relation : If at the time the machine is in state , the reading head is on tape cell , and the symbol is in tape cell , then at the time the machine is in a state , the reading head is on a tape cell , and a symbol is in tape cell , so that is true. ${\displaystyle \Delta }$ ${\displaystyle t}$ ${\displaystyle q}$ ${\displaystyle z}$ ${\displaystyle z}$ ${\displaystyle a}$ ${\displaystyle t+1}$ ${\displaystyle q^{\prime }}$ ${\displaystyle z+z^{\prime }}$ ${\displaystyle z}$ ${\displaystyle a\prime }$ ${\displaystyle (q,a,q^{\prime },a^{\prime },z^{\prime })\in \Delta }$
4. At the end there is an accepting end state. ${\displaystyle M}$
5. There is exactly one state at any point in time . ${\displaystyle t}$ ${\displaystyle M}$
6. At any point in time , the read head is located on exactly one belt cell. ${\displaystyle t}$
7. At any point in time there is exactly one symbol in each band cell . ${\displaystyle t}$ ${\displaystyle z}$
8. If the reading head is not at the tape cell at the time, this tape cell still contains the same character at the time . ${\displaystyle t}$ ${\displaystyle z}$ ${\displaystyle t+1}$

The first sub-statement describes , the sub-statements 2 to 4 describe , and the sub-statements 5 to 8 describe the rules for nondeterministic Turing machines. The question of whether there is a satisfactory assignment for the Boolean variables is now equivalent to the question of whether there is an accepting run of when input . ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle x}$

Impetus for science

→ Main article : P-NP problem

In 1971, Cook presented his work entitled The complexity of theorem-proving procedures at the American Annual ACM Symposium on Theory of Computing (STOC) . In the following years, complexity theory gained in importance and the question moved to the center of research in theoretical computer science. Articles appear on this in the spectrum of science, in the New York Times, in the Spiegel, in the Frankfurter Allgemeine Zeitung, in the time and many others. In the 80s the complexity theory experienced its main heyday. The Structures in Complexity conference, which takes place every year in different locations around the world, was founded. ${\displaystyle {\mathsf {NP}}\neq {\mathsf {P}}}$

See also

• List of theorems of computer science

literature

• Stephen A. Cook: The complexity of theorem-proving procedures . In: Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing (STOC'71) . ACM, New York 1971, pp. 151-158.
• Leonid Levin: Universal sorting problems . In: Problems of Information Transmission , Vol. 9 (1973), pp. 265-266, ISSN  0032-9460 .
• Richard M. Karp: Reducibility among combinatorial problems . In: James W. Thatcher, Raymond E. Miller (Eds.): Complexity of Computer Computations . Plenum Press, New York 1972, ISBN 0-306-30707-3 .

Web links

• Detailed proof on Grundstudium.info