Gourt Home::Gourt :: 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 beweist, dass das Erfüllbarkeitsproblem der Aussagenlogik, SAT (engl.: Satisfiability) zu NPC gehört. Einen vergleichbaren Satz veröffentlichte L. 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 Turingmaschine in polynomieller Zeit gelöst werden. Die Idee des Beweises ist nun, sämtliche Bedingungen, die an eine solche Turingmaschine gestellt werden, in aussagenlogische Formeln zu packen. Dies sind (nicht vollständig) folgende Bedingungen:
- Es kann nur ein Zustand q zu einem Zeitpunkt t aktiv sein
- Wenn zum Zeitpunkt t Zustand q aktiv ist und Zeichen a gelesen wird, dann ist durch die Übergangsfunktion Zustand q' zum Zeitpunkt t+1 definiert (q' kann aufgrund der Eigenschaft des Nichtdeterminismus der Maschine aus einer Menge von Möglichen Folgezuständen geraten werden, eine deterministische Turingmaschine hätte im Vergleich dazu nur je maximal einen Folgezustand, wodurch dieser eindeutig ist, falls vorhanden)
- Am Ende muss mindestens ein Endzustand erreicht werden können
- Auf jedem Bandquadrat kann nur ein Zeichen stehen.
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 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 gegründet: Structures in Complexity.
Weblinks
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.
Cook's theorem | Teorema de Cook | Théorème de Cook | משפט קוק-לוין | Teorema di Cook | Twierdzenie Cooka
"Satz von Cook"