Satz von Cook

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.

Inhaltsverzeichnis

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

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.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Satz von Shamir — In der theoretischen Informatik ist Vollständigkeit eine Eigenschaft von Problemen in Bezug auf eine Komplexitätsklasse. Intuitiv ist ein Problem dann vollständig für eine bestimmte Komplexitätsklasse, wenn kein anderes Problem der Klasse… …   Deutsch Wikipedia

  • Cook (Familienname) — Cook ist ein Familienname. Bekannte Namensträger Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z …   Deutsch Wikipedia

  • Cook — steht für: Cook (Familienname), der Familienname Cook Cook Group, Hersteller medizinischer Geraete Cook Gletscher, zwei Gletscher auf subantarktischen Inseln Cook Insel (Südsandwichinseln), Insel der zu den Südsandwichinseln gehörenden… …   Deutsch Wikipedia

  • Satz vom Nullprodukt — Die Multiplikation (v. lat.: multiplicare = vervielfachen, auch Malnehmen genannt) ist eine der vier Grundrechenarten in der Arithmetik. Inhaltsverzeichnis 1 Namensgebung 2 Rechengesetze 2.1 Gaußsche Summenfaktor Regel 3 …   Deutsch Wikipedia

  • Stephen Arthur Cook — Stephen A. Cook 2008 Stephen Arthur Cook (* 14. Dezember 1939 in Buffalo, New York) ist Professor der Informatik an der University of Toronto in Kanada. Sein Hauptbetätigungsfeld ist die Komplexitätstheorie; Cook arbeitet neben seiner… …   Deutsch Wikipedia

  • Stephen Cook — Stephen A. Cook 2008 Stephen Arthur Cook (* 14. Dezember 1939 in Buffalo, New York) ist Professor der Informatik an der University of Toronto in Kanada. Sein Hauptbetätigungsfeld ist die Komplexitätstheorie; Cook arbeitet neben seiner… …   Deutsch Wikipedia

  • Stephen A. Cook — 2008 Stephen Arthur Cook (* 14. Dezember 1939 in Buffalo, New York) ist Professor der Informatik an der University of Toronto in Kanada. Sein Hauptbetätigungsfeld ist die Komplexitätstheorie; Cook arbeitet neben seiner Lehrtätigkeit aber auch an… …   Deutsch Wikipedia

  • Liste von Sätzen der Informatik — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z C Satz von Cook: Es existiert eine Teilmenge von …   Deutsch Wikipedia

  • Etymologie von Firmennamen — Dies ist eine Liste von Unternehmensnamen (Firmen) und ihrer Herkunft (Etymologie). # 20th Century Fox gebildet 1935 durch die Fusion William Fox’ Fox Film und Twentieth Century Pictures. 3M Die Minnesota Mining and Manufacturing Company (etwa… …   Deutsch Wikipedia

  • Etymologische Liste von Unternehmensnamen — Dies ist eine Liste von Unternehmensnamen (Firmen) und ihrer Herkunft (Etymologie). # 20th Century Fox gebildet 1935 durch die Fusion William Fox’ Fox Film und Twentieth Century Pictures. 3M Die Minnesota Mining and Manufacturing Company (etwa… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”