Satz von Cook

Der kanadische Wissenschaftler Stephen A. Cook begründete 1971 eine neue Klasse von Problemen in der Komplexitätstheorie. Er zeigte, dass eine Teilmenge der Klasse NP existiert, auf die sich alle Probleme aus NP polynomiell reduzieren lassen. Diese Teilmenge ist damit repräsentativ für die Schwierigkeit von NP und wird als NP-vollständig (NPC für engl.: NP complete) bezeichnet. Der nach ihm benannte Satz von Cook sagt aus, dass das Erfüllbarkeitsproblem der Aussagenlogik, SAT (engl.: Satisfiability), NP-vollständig ist. Einen vergleichbaren Satz veröffentlichte Leonid Levin unabhängig von Cook im Jahre 1973, deswegen spricht man manchmal auch vom Satz von Cook und Levin.

Mit einem bekannten Vertreter der Klasse war der Nachweis für andere Probleme aus NP wesentlich einfacher zu führen, da es für ein Problem M aus NP nun ausreichte eine polynomielle Reduktion von SAT auf M zu konstruieren, um die NP-Vollständigkeit von M zu beweisen. Richard M. Karp erweiterte 1972 auf diese Weise NPC um 21 weitere Probleme, bis heute wurden mehrere hundert nachgewiesen.

Beweisskizze

Angenommen, L ist eine beliebige Sprache in NP. Wir konstruieren eine Reduktion von L auf SAT, d.h. wir beschreiben, wie wir aus einer Zeichenkette x in Polynomialzeit eine aussagenlogische Formel berechnen können, welche genau dann erfüllbar ist, wenn $x \in L$. Weil L in NP liegt, gibt es eine nichtdeterministische Turingmaschine M, welche in Polynomialzeit entscheidet, ob x zur Sprache L gehört. Die Grundidee der Reduktion ist nun, die Aussage „Die Berechnung der Maschine M bei Eingabe x ergibt, dass x zur Sprache L gehört“ in einer aussagenlogischen Formel auszudrücken. In dieser Formel müssen sich also eine Beschreibung der Maschine M, eine Beschreibung der Eingabe x sowie die „Rechenregeln“, nach denen eine nichtdeterministische Turingmaschine arbeitet, wiederfinden.

Dazu verwenden wir die folgenden drei Familien boolescher Variablen:

• Q[t,q] Interpretation: Die Turing-Maschine befindet sich zum Zeitpunkt t im Zustand q.
• H[t,z] Interpretation: Der Lesekopf der Turing-Maschine befindet sich zum Zeitpunkt t an der Bandzelle z.
• S[t,z,a] Interpretation: Zum Zeitpunkt t steht in der Bandzelle z der Turing-Maschine das Symbol a.

Dabei sind nur diejenigen Bandzellen z von Bedeutung, welche der Lesekopf tatsächlich erreicht. Da eine Turingmaschine den Lesekopf in einem Rechenschritt nur um eine Bandzelle bewegen kann, ist durch die Anzahl der Rechenschritte auch die Anzahl der erreichbaren Bandzellen beschränkt.

Die Formel besteht nun aus folgenden Teilaussagen, welche alle jeweils durch UND verknüpft werden.

1. Zu Beginn stehen in den Bandzellen die Symbole von x, umgeben von Leerzeichen.
2. Zu Beginn befindet sich M im Startzustand
3. M hält seine Zustandsübergangsrelation Δ ein: Wenn sich zum Zeitpunkt t die Maschine in Zustand q, der Lesekopf an Bandzelle z, und in Bandzelle z das Symbol a befindet, so befindet sich zum Zeitpunkt t + 1 die Maschine in einem Zustand q', der Lesekopf an einer Bandzelle z', und in Bandzelle z ein Symbol a', so dass $(q,a,q',a',z') \in \Delta$ gilt.
4. Am Ende befindet sich M in einem akzeptierenden Endzustand
5. Zu jedem Zeitpunkt t befindet sich M in genau einem Zustand
6. Zu jedem Zeitpunkt t befindet sich der Lesekopf an genau einer Bandzelle
7. Zu jedem Zeitpunkt t befindet sich in jeder Bandzelle z genau ein Symbol
8. Befindet sich der Lesekopf zum Zeitpunkt t nicht an Bandzelle z, so enthält diese Bandzelle zum Zeitpunkt t + 1 noch immer dasselbe Zeichen.

Die erste Teilaussage beschreibt x, die Teilaussagen 2-4 beschreiben M, und die Teilaussagen 5-8 beschreiben die „Rechenregeln“ für nichtdeterministische Turingmaschinen. Die Frage, ob es eine erfüllende Belegung für die booleschen Variablen gibt, ist nun gleichwertig mit der Frage, ob es einen akzeptierenden Lauf von M bei Eingabe x gibt.

Impulse für die Wissenschaft

Im Jahr 1971 trug Cook über seine Arbeit mit dem Titel The complexity of theorem-proving procedures auf dem amerikanischen Annual ACM Symposium on Theory of Computing (STOC) vor. In den folgenden Jahren gewann die Komplexitätstheorie stark an Bedeutung und die Frage $\mathsf{NP}\not= \mathsf{P}$ (siehe P-NP-Problem) rückte in den Mittelpunkt der Forschung der Theoretischen Informatik. Es erscheinen hierzu Artikel im Spektrum der Wissenschaften, in der New York Times, im Spiegel, in der Frankfurter Allgemeinen Zeitung, in der Zeit und vielen anderen. In den 80er Jahren erlebt die Komplexitätstheorie ihre Hauptblütezeit. Es wird die jährlich weltweit an wechselnden Orten stattfindende Tagung Structures in Complexity gegründet.

Weblinks

• Ausführlicher Beweis auf Grundstudium.info

Literatur

• S. A. Cook. The complexity of theorem-proving procedures, in Proceedings of ACM STOC'71, pp. 151-158, 1971.
• L. A. Levin.. Universal sorting problems, Problems of Information Transmission, 9, S. 265-266, 1973.
• Richard M. Karp Reducibility among combinatorial problems, in Complexity of Computer Computations (J. W. Thatcher and R. E. Miller, eds.), Plenum Press, 1972.