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 reduzieren lassen. Diese Teilmenge ist damit repräsentativ für die Schwierigkeit von NP und wird als NP-vollständig (NPC für englisch NP complete) bezeichnet. Der nach ihm benannte Satz von Cook sagt aus, dass das Erfüllbarkeitsproblem der Aussagenlogik (SAT, v. 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

Sei ${\displaystyle L}$ eine beliebige Sprache in NP. Es ist nun eine Reduktion von ${\displaystyle L}$ auf SAT zu konstruieren, d. h. eine Beschreibung, wie aus einer Zeichenkette ${\displaystyle x}$ in Polynomialzeit eine aussagenlogische Formel berechnet werden kann, welche genau dann erfüllbar ist, wenn ${\displaystyle x\in L}$. Weil ${\displaystyle L}$ in NP liegt, gibt es eine nichtdeterministische Turingmaschine ${\displaystyle M}$, die in Polynomialzeit entscheidet, ob ${\displaystyle x}$ zur Sprache ${\displaystyle L}$ gehört. Die Grundidee der Reduktion ist nun, die Aussage, dass die Berechnung der Maschine ${\displaystyle M}$ bei Eingabe ${\displaystyle x}$ ergibt, dass ${\displaystyle x}$ zur Sprache ${\displaystyle L}$ gehört, in einer aussagenlogischen Formel auszudrücken. In dieser Formel müssen sich also eine Beschreibung der Maschine ${\displaystyle M}$, eine Beschreibung der Eingabe ${\displaystyle x}$ sowie die Regeln, nach denen eine nichtdeterministische Turingmaschine arbeitet, wiederfinden.

Dazu verwenden wir diese drei Familien boolescher Variablen mit der jeweils nachfolgend angegebenen Interpretation:

• ${\displaystyle Q[t,q]}$: Die Turing-Maschine befindet sich zum Zeitpunkt ${\displaystyle t}$ im Zustand ${\displaystyle q}$ und keinem anderen.
• ${\displaystyle H[t,z]}$: Der Lesekopf der Turing-Maschine befindet sich zum Zeitpunkt ${\displaystyle t}$ an der Bandzelle ${\displaystyle z}$ und keinem anderen.
• ${\displaystyle S[t,z,a]}$: Zum Zeitpunkt ${\displaystyle t}$ steht in der Bandzelle ${\displaystyle z}$ der Turing-Maschine das Symbol ${\displaystyle a}$ und kein anderes.

Dabei sind nur diejenigen Bandzellen 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 Klauseln:

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

Die erste Teilaussage beschreibt ${\displaystyle x}$, die Teilaussagen 2 bis 4 beschreiben ${\displaystyle M}$, und die Teilaussagen 5 bis 8 beschreiben die Regeln 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 ${\displaystyle M}$ bei Eingabe ${\displaystyle 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 ${\displaystyle {\mathsf {NP}}\neq {\mathsf {P}}}$ 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 erlebte die Komplexitätstheorie ihre Hauptblütezeit. Es wurde die jährlich weltweit an wechselnden Orten stattfindende Tagung Structures in Complexity gegründet.

Siehe auch

• Liste von Sätzen der Informatik

Literatur

• Leonid Levin: Universal sorting problems. In: Problems of Information Transmission, Jg. 9 (1973), S. 265–266, ISSN 0032-9460.
• 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, S. 151–158.
• Richard M. Karp: Reducibility among combinatorial problems. In: James W. Thatcher, Raymond E. Miller (Hrsg.): Complexity of Computer Computations. Plenum Press, New York 1972, ISBN 0-306-30707-3.

Weblinks

• Ausführlicher Beweis auf Grundstudium.info