Cook–Levin theorem

The Canadian scientist Stephen A. Cook founded in 1971, a new class of problems in complexity theory. He showed that a portion of the class NP exists, can not be reduced to all problems from NP. This subset is thus representative of the difficulty of NP and is NP- complete ( NPC for engl: NP complete. ) Respectively. The eponymous set of Cook says that the satisfiability of propositional logic, SAT (English: satisfiability ) is NP -complete. A comparable set of published Leonid Levin independently by Cook in 1973, so sometimes this is described as set of Cook and Levin.

With a well-known representative of the class of evidence of other problems from NP was much easier to perform, since it is a problem of NP M now enough a polynomial reduction from SAT to M to construct, to prove the NP- completeness of M. Richard M. Karp extended in 1972 in this way NPC to 21 additional problems until today, several hundred were detected.

Sketch of proof

Suppose L is an arbitrary language in NP. We construct a reduction from L to SAT, ie we describe how we can compute x a propositional formula from a string in polynomial time, which is satisfiable if. Because L is in NP, there is a non-deterministic Turing machine M that decides in polynomial time whether x belongs to the language L. The basic idea of ​​the reduction is now, the statement " The machine M on input x calculation shows that x belongs to the language L " in a propositional formula expressing. In this formula, therefore, must find a description of the machine M, a description of the input x and the " computation rules " according to which a non-deterministic Turing machine works.

We use the following three families of Boolean variables:

• Q [t, q] Interpretation: The Turing machine is in state q at time t.
• H [t, z] Interpretation: The read head of the Turing machine is located at time t at the tape cell for
• S [ t, z, a] Interpretation: At time t is in the tape cell z of the Turing machine, the symbol a

In this case, only those tape cells z of meaning which actually reaches the read head. Since a Turing machine can move the read head in a computation step only one tape cell, the number of reachable tape cells is limited by the number of computational steps.

The formula now consists of the following sub-statements, which are linked by AND all each.

The first part describes statement x, the partial statements 2-4 describe M and the partial statements 5-8 describe the " computation rules " for nondeterministic Turing machines. The question of whether there is a satisfying assignment for the Boolean variables, is now equivalent to the question of whether there is an accepting run x of M on input.

Initiate new research

In 1971, Cook was wearing on his work entitled The complexity of theorem - proving procedures on the American Annual ACM Symposium on Theory of Computing ( STOC ) ago. In the following years the complexity theory gained significantly in importance and the question (see P - NP problem ) became the focus of research in theoretical computer science. It appears this article in the spectrum of the sciences, in the New York Times, in the mirror, in the Frankfurter Allgemeine Zeitung, in time, and many others. In the 80s, the complexity theory experienced their main flowering period. It is established in the world held annually at different locations meeting Structures in Complexity.