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 beweist, 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.
Mit einem bekannten Vertreter der Klasse war der Nachweis für andere Probleme aus NP wesentlich einfacher zu führen, da bei ihnen nur noch die polynomielle Reduzierbarkeit von SAT nachgewiesen zu werden braucht. Richard M. Karp erweiterte 1972 auf diese Weise NPC um 21 weitere Probleme, bis heute wurden mehrere hundert nachgewiesen.
Beweisskizze
Jedes Problem der Klasse NP kann durch eine nicht-deterministische oder auch randomisierte Turingmaschine in polynomieller Zeit gelöst werden. Die folgende Beweisskizze bezieht sich auf eine randomisierte Turing-Maschine. Die Idee des Beweises ist nun, sämtliche sechs Bedingungen, die an eine solche Turingmaschine gestellt werden, in aussagenlogische Formeln zu bringen.
Beschreiben lässt sich eine randomisierte Turing-Maschine über die folgenden drei booleschen Variablen:
- Q[i,k] Bedeutung: Die Turing-Maschine befindet sich zum Zeitpunkt i im Zustand k.
- H[i,j] Bedeutung: Der Lesekopf der Turing-Maschine befindet sich zum Zeitpunkt i in der Bandzelle j.
- S[i,j,l] Bedeutung: Zum Zeitpunkt i steht in der Bandzelle j der Turing-Maschine das Symbol l.
Die folgenden sechs Bedingungen für eine korrekte Arbeitsweise der randomisierten Turing-Maschine müssen nun in solche aussagenlogische Formeln gegossen werden. Nur wenn all diese Formeln erfüllt werden, akzeptiert die randomisierte Turing-Maschine das Wort, das zur formalen Sprache gehört.
- Die Turing-Maschine ist zu jedem Zeitpunkt i in genau einem Zustand q.
- Der Lesekopf der Turing-Maschine steht zu jedem Zeitpunkt i über genau einer Bandzelle j.
- Zum Zeitpunkt i enthält die Bandzelle j der Turing-Maschine genau ein Symbol l.
- Zum Zeitpunkt 0 befindet sich die Turing-Maschine im Ausgangs-/Startzustand.
- Zum Zeitpunkt p(n) (p Polynom) befindet sich die Turing-Maschine im Endzustand und akzeptiert die Eingabe.
- Die Konfiguration zum Zeitpunkt (i+1) wird durch die Konfiguration zum Zeitpunkt i und die Übergangsfunktion (δ) definiert.
Für die korrekte Arbeitsweise der Turing-Maschine – wie oben beschrieben – müssen alle sechs Formeln erfüllt sein. Diese lassen sich mithilfe der oben definierten drei booleschen Variablen ausdrücken (nicht näher spezifiziert). Da es sich um eine randomisierte Turingmaschine handelt, kann sie nur polynomiell viele Schritte machen. Daher kann die aussagenlogischen Formel in Polynomialzeit konstruiert werden.
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 (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
Literatur
- S. A. Cook. The complexity of theorem-proving procedures, in Proceedings of ACM STOC'71, pp. 151-158, 1971. (pdf.gz)
- 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.