Satz von Cook

mathematischer Satz

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

Bearbeiten

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

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

  •  : Die Turing-Maschine befindet sich zum Zeitpunkt   im Zustand   und keinem anderen.
  •  : Der Lesekopf der Turing-Maschine befindet sich zum Zeitpunkt   an der Bandzelle   und keinem anderen.
  •  : Zum Zeitpunkt   steht in der Bandzelle   der Turing-Maschine das Symbol   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  , umgeben von Leerzeichen.
  2. Zu Beginn befindet sich   im Startzustand.
  3.   hält seine Zustandsübergangsrelation   ein: Wenn sich zum Zeitpunkt   die Maschine in Zustand  , der Lesekopf an Bandzelle  , und in Bandzelle   das Symbol   befindet, so befindet sich zum Zeitpunkt   die Maschine in einem Zustand  , der Lesekopf an einer Bandzelle  , und in Bandzelle   ein Symbol  , so dass   gilt.
  4. Am Ende befindet sich   in einem akzeptierenden Endzustand.
  5. Zu jedem Zeitpunkt   befindet sich   in genau einem Zustand.
  6. Zu jedem Zeitpunkt   befindet sich der Lesekopf an genau einer Bandzelle.
  7. Zu jedem Zeitpunkt   befindet sich in jeder Bandzelle   genau ein Symbol.
  8. Befindet sich der Lesekopf zum Zeitpunkt   nicht an Bandzelle  , so enthält diese Bandzelle zum Zeitpunkt   noch immer dasselbe Zeichen.

Die erste Teilaussage beschreibt  , die Teilaussagen 2 bis 4 beschreiben  , 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   bei Eingabe   gibt.

Impulse für die Wissenschaft

Bearbeiten

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   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

Bearbeiten

Literatur

Bearbeiten
  • 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.
  • Leonid Levin: Universal sorting problems. In: Problems of Information Transmission, Jg. 9 (1973), S. 265–266, ISSN 0032-9460.
  • 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.
Bearbeiten