www.wikidata.de-de.nina.az

Satz von Cook Der kanadische Wissenschaftler Stephen A Cook begründete 1971 eine neue Klasse von Problemen in der Komple

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

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der kanadische Wissenschaftler Stephen A Cook begrundete 1971 eine neue Klasse von Problemen in der Komplexitatstheorie Er zeigte dass eine Teilmenge der Klasse NP existiert auf die sich alle Probleme aus NP reduzieren lassen Diese Teilmenge ist damit reprasentativ fur die Schwierigkeit von NP und wird als NP vollstandig NPC fur englisch NP complete bezeichnet Der nach ihm benannte Satz von Cook sagt aus dass das Erfullbarkeitsproblem der Aussagenlogik SAT v engl satisfiability NP vollstandig ist Einen vergleichbaren Satz veroffentlichte Leonid Levin unabhangig 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 fur andere Probleme aus NP wesentlich einfacher zu fuhren da es fur ein Problem M aus NP nun ausreichte eine polynomielle Reduktion von SAT auf M zu konstruieren um die NP Vollstandigkeit von M zu beweisen Richard M Karp erweiterte 1972 auf diese Weise NPC um 21 weitere Probleme bis heute wurden mehrere hundert nachgewiesen Inhaltsverzeichnis 1 Beweisskizze 2 Impulse fur die Wissenschaft 3 Siehe auch 4 Literatur 5 WeblinksBeweisskizze BearbeitenSei L displaystyle L nbsp eine beliebige Sprache in NP Es ist nun eine Reduktion von L displaystyle L nbsp auf SAT zu konstruieren d h eine Beschreibung wie aus einer Zeichenkette x displaystyle x nbsp in Polynomialzeit eine aussagenlogische Formel berechnet werden kann welche genau dann erfullbar ist wenn x L displaystyle x in L nbsp Weil L displaystyle L nbsp in NP liegt gibt es eine nichtdeterministische Turingmaschine M displaystyle M nbsp die in Polynomialzeit entscheidet ob x displaystyle x nbsp zur Sprache L displaystyle L nbsp gehort Die Grundidee der Reduktion ist nun die Aussage dass die Berechnung der Maschine M displaystyle M nbsp bei Eingabe x displaystyle x nbsp ergibt dass x displaystyle x nbsp zur Sprache L displaystyle L nbsp gehort in einer aussagenlogischen Formel auszudrucken In dieser Formel mussen sich also eine Beschreibung der Maschine M displaystyle M nbsp eine Beschreibung der Eingabe x displaystyle x nbsp sowie die Regeln nach denen eine nichtdeterministische Turingmaschine arbeitet wiederfinden Dazu verwenden wir diese drei Familien boolescher Variablen mit der jeweils nachfolgend angegebenen Interpretation Q t q displaystyle Q t q nbsp Die Turing Maschine befindet sich zum Zeitpunkt t displaystyle t nbsp im Zustand q displaystyle q nbsp und keinem anderen H t z displaystyle H t z nbsp Der Lesekopf der Turing Maschine befindet sich zum Zeitpunkt t displaystyle t nbsp an der Bandzelle z displaystyle z nbsp und keinem anderen S t z a displaystyle S t z a nbsp Zum Zeitpunkt t displaystyle t nbsp steht in der Bandzelle z displaystyle z nbsp der Turing Maschine das Symbol a displaystyle a nbsp und kein anderes Dabei sind nur diejenigen Bandzellen von Bedeutung welche der Lesekopf tatsachlich 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 beschrankt Die Formel besteht nun aus folgenden Klauseln Zu Beginn stehen in den Bandzellen die Symbole von x displaystyle x nbsp umgeben von Leerzeichen Zu Beginn befindet sich M displaystyle M nbsp im Startzustand M displaystyle M nbsp halt seine Zustandsubergangsrelation D displaystyle Delta nbsp ein Wenn sich zum Zeitpunkt t displaystyle t nbsp die Maschine in Zustand q displaystyle q nbsp der Lesekopf an Bandzelle z displaystyle z nbsp und in Bandzelle z displaystyle z nbsp das Symbol a displaystyle a nbsp befindet so befindet sich zum Zeitpunkt t 1 displaystyle t 1 nbsp die Maschine in einem Zustand q displaystyle q prime nbsp der Lesekopf an einer Bandzelle z z displaystyle z z prime nbsp und in Bandzelle z displaystyle z nbsp ein Symbol a displaystyle a prime nbsp so dass q a q a z D displaystyle q a q prime a prime z prime in Delta nbsp gilt Am Ende befindet sich M displaystyle M nbsp in einem akzeptierenden Endzustand Zu jedem Zeitpunkt t displaystyle t nbsp befindet sich M displaystyle M nbsp in genau einem Zustand Zu jedem Zeitpunkt t displaystyle t nbsp befindet sich der Lesekopf an genau einer Bandzelle Zu jedem Zeitpunkt t displaystyle t nbsp befindet sich in jeder Bandzelle z displaystyle z nbsp genau ein Symbol Befindet sich der Lesekopf zum Zeitpunkt t displaystyle t nbsp nicht an Bandzelle z displaystyle z nbsp so enthalt diese Bandzelle zum Zeitpunkt t 1 displaystyle t 1 nbsp noch immer dasselbe Zeichen Die erste Teilaussage beschreibt x displaystyle x nbsp die Teilaussagen 2 bis 4 beschreiben M displaystyle M nbsp und die Teilaussagen 5 bis 8 beschreiben die Regeln fur nichtdeterministische Turingmaschinen Die Frage ob es eine erfullende Belegung fur die booleschen Variablen gibt ist nun gleichwertig mit der Frage ob es einen akzeptierenden Lauf von M displaystyle M nbsp bei Eingabe x displaystyle x nbsp gibt Impulse fur die Wissenschaft Bearbeiten Hauptartikel P NP Problem Im Jahr 1971 trug Cook uber 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 Komplexitatstheorie stark an Bedeutung und die Frage N P P displaystyle mathsf NP neq mathsf P nbsp ruckte 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 Komplexitatstheorie ihre Hauptblutezeit Es wurde die jahrlich weltweit an wechselnden Orten stattfindende Tagung Structures in Complexity gegrundet Siehe auch BearbeitenListe von Satzen der InformatikLiteratur BearbeitenStephen 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 Weblinks BearbeitenAusfuhrlicher Beweis auf Grundstudium info Abgerufen von https de wikipedia org w index php title Satz von Cook amp oldid 167499785