Die Klassen P und NP
Lesen anpassen
Nach dieser Lektion kannst du
ein Problem als Entscheidungsproblem, also als Sprache über einem Alphabet, aufschreiben und die Länge seiner Kodierung bestimmen,
die Klasse P definieren und begründen, warum Polynomialzeit als Grenze für „effizient“ dient und wo dieses Modell hinkt,
NP über Zertifikate und Verifizierer erklären und für SAT, Hamiltonkreis, Clique und Subset-Sum einen Verifizierer angeben,
die Gleichwertigkeit mit nichtdeterministischen Turingmaschinen in ihren Grundzügen begründen,
pseudopolynomielle Laufzeit wie beim Rucksackproblem von polynomieller Laufzeit unterscheiden.
Vorausgesetzt: Laufzeit messen: Operationen zählen und O-Notation, Turingmaschinen, Das 0/1-Rucksackproblem
Auf einem Lagertisch liegen sechs Pakete mit den Gewichten 3, 34, 4, 12, 5 und 2 Kilogramm. Ein Kurier soll genau 9 Kilogramm mitnehmen. Geht das?
Den Vorschlag „4 und 5“ prüfst du mit einer Addition. Ohne Vorschlag musst du suchen: Sechs Pakete haben Teilmengen, 60 Pakete schon . Es gibt geschicktere Verfahren als dieses Durchprobieren, aber keines ist bekannt, dessen Schrittzahl für alle Eingaben nur polynomiell mit der Länge der Eingabe wächst.
Eine Lösung finden und eine vorgeschlagene Lösung prüfen sind also verschiedene Tätigkeiten. Daraus macht die Komplexitätstheorie zwei Klassen: P für effizient lösbare Probleme, NP für Probleme mit effizient prüfbaren Lösungen. Ob beide gleich sind, ist eine der bekanntesten offenen Fragen der Mathematik.
Ein Rechner prüft Teilmengen pro Sekunde. Wie lange braucht er ungefähr, um alle Teilmengen von 60 Paketen durchzugehen?
Entscheidungsproblem und Kodierung
Ein Alphabet ist eine endliche, nicht leere Menge von Zeichen, meist . ist die Menge aller endlichen Wörter über , und ist die Länge des Wortes .
Ein Entscheidungsproblem ist eine Frage, deren Antwort nur „ja“ oder „nein“ ist. Jede Eingabe (eine Instanz) schreiben wir als Wort , die Kodierung von . Das Problem ist dann die Sprache der Ja-Instanzen:
.
Das Problem lösen heißt, zu entscheiden: Eine Turingmaschine hält bei jeder Eingabe und akzeptiert genau dann, wenn . Die Laufzeit messen wir in der Eingabelänge .
Wie lang ist eine Eingabe?
Wie lang ist eine Eingabe?
| Objekt | Kodierung | Länge |
|---|---|---|
| Zahl , binär | ||
| Zahl , unär | tausend Einsen | |
| Zahl , binär | Binärdarstellung | |
| Graph mit Knoten | Adjazenzmatrix Zeile für Zeile | |
| Subset-Sum mit Zahlen bis | alle Zahlen binär, durch Trennzeichen getrennt | etwa |
Die Adjazenzmatrix eines Graphen hat in Zeile , Spalte eine , wenn es eine Kante zwischen Knoten und Knoten gibt, sonst eine .
Übliche Kodierungen (Adjazenzmatrix, Adjazenzliste) unterscheiden sich in der Länge nur polynomiell, für „polynomiell oder nicht“ ist die Wahl also egal. Die Ausnahme sind Zahlen: Unär geschrieben ist eine Zahl exponentiell länger als binär. Wir schreiben Zahlen deshalb immer binär.
Laufzeit einer Turingmaschine und die Klasse P
Sei eine deterministische Turingmaschine, die bei jeder Eingabe hält. Ihre Laufzeit ist die größte Zahl von Schritten, die auf einer Eingabe der Länge macht (der ungünstigste Fall).
ist die Menge der Sprachen, die eine deterministische Turingmaschine mit Laufzeit entscheidet. Die Klasse P besteht aus allen Sprachen, die in Polynomialzeit entscheidbar sind, also in Zeit für eine feste Zahl :
Probleme in P
Probleme in P
- Erreichbarkeit: Gibt es einen Weg von nach ? Breitensuche, bei Knoten und Kanten (auf einer Turingmaschine ein größeres Polynom).
- Zweifärbbarkeit: Lassen sich die Knoten so mit zwei Farben färben, dass jede Kante zwei verschiedene Farben verbindet? Die Breitensuche färbt abwechselnd und findet jeden Widerspruch.
- Kürzeste Wege: Gibt es einen Weg von nach mit Gewicht höchstens ? Bei nichtnegativen Kantengewichten Dijkstra, polynomiell auch in der Länge der binär geschriebenen Gewichte.
- Primzahltest: Ist die binär gegebene Zahl prim? Polynomiell seit dem Algorithmus von Agrawal, Kayal und Saxena (2002).
Ein Optimierungsproblem („Wie kurz ist der kürzeste Weg?“) wird zum Entscheidungsproblem, indem man eine Schranke in die Eingabe aufnimmt. Den optimalen Wert findet man dann meist durch binäre Suche über .
Der Test „Teile durch alle Zahlen von 2 bis “ braucht etwa Divisionen. Ist er ein Polynomialzeit-Verfahren für den Primzahltest?
Robustheit von P
Entscheidet eine Turingmaschine mit mehreren Bändern eine Sprache in Zeit , dann entscheidet eine Turingmaschine mit einem Band sie in Zeit . Ebenso simulieren Turingmaschinen die üblichen Rechnermodelle mit wahlfreiem Speicherzugriff (wenn eine Operation auf -Bit-Zahlen etwa Schritte kostet) mit polynomiellem Mehraufwand. P hängt deshalb nicht vom gewählten Modell ab.
Wir skizzieren den ersten Teil. Die Einband-Maschine schreibt die Bandinhalte nebeneinander, getrennt durch , und markiert jede Kopfposition. Für einen simulierten Schritt läuft sie einmal über alles, liest die markierten Zeichen und läuft ein zweites Mal, um sie zu ändern und die Markierungen zu verschieben (wird ein Abschnitt länger, rückt der Rest eine Zelle weiter).
In Schritten wächst jedes Band um höchstens Zellen, und . Der belegte Teil ist also lang, ein simulierter Schritt kostet bei festem also , insgesamt . Mit ist auch ein Polynom.
Verifizierer und die Klasse NP
Ein Verifizierer für eine Sprache ist eine deterministische Turingmaschine , die Paare liest und bei jeder Eingabe hält. Das zweite Wort heißt Zertifikat (oder Zeuge). Es gilt:
es gibt ein mit , sodass das Paar akzeptiert.
Dabei ist ein Polynom. Die Klasse NP besteht aus allen Sprachen, die einen Verifizierer mit Laufzeit polynomiell in besitzen.
Für jedes muss es ein passendes Zertifikat geben, für darf keines funktionieren, wie geschickt es auch gewählt ist.
Vier Probleme in NP
Vier Probleme in NP
- SAT: Ist eine aussagenlogische Formel erfüllbar, gibt es also eine Belegung der Variablen mit wahr und falsch, unter der wahr ist?
- Hamiltonkreis: Hat ein ungerichteter Graph einen Kreis, der jeden Knoten genau einmal besucht?
- Clique: Hat ein Graph eine Clique der Größe , also Knoten, die paarweise durch Kanten verbunden sind?
- Subset-Sum: Gibt es zu natürlichen Zahlen und einem Ziel eine Teilmenge der Indizes, deren Zahlen sich genau zu summieren?
| Problem | Zertifikat | Prüfung |
|---|---|---|
| SAT | eine Belegung der Variablen | auswerten, linear in der Formellänge |
| Hamiltonkreis | eine Reihenfolge der Knoten | jeder Knoten einmal, Nachbarn in der Folge benachbart |
| Clique | eine Menge von Knoten | alle Paare in der Adjazenzmatrix nachsehen |
| Subset-Sum | eine Teilmenge der Indizes | die ausgewählten Zahlen binär addieren und mit vergleichen |
Jedes Zertifikat ist polynomiell lang, jede Prüfung polynomiell, also liegen alle vier Probleme in NP. Für das Paketproblem vom Anfang sind und Zertifikate.
Ein Verifizierer für Hamiltonkreis
Ein Verifizierer für Hamiltonkreis
Die Eingabe ist ein Graph mit Knoten als Adjazenzmatrix , das Zertifikat eine Folge von Knotennummern.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 2 | |
| 6 | 2 | |
| 7 | 1 | |
| 8 | 2 | |
| 9 | 2 | |
| 10 | 1 |
Zeile 2: Ein Kreis ohne Mehrfachkanten hat mindestens drei Knoten. Die erste Schleife stellt sicher, dass jeder Knoten genau einmal vorkommt, die zweite prüft die Kanten des Kreises einschließlich der Rückkante von zu .
Das sind Prüfungen, also polynomiell viele Schritte. Bemerkenswert ist, was der Verifizierer nicht kann: Ein allgemeines System polynomiell langer, effizient prüfbarer Zertifikate für alle Graphen ohne Hamiltonkreis ist nicht bekannt. Einzelne Nein-Instanzen können dagegen leicht beweisbar sein.
Welches Zertifikat eignet sich für Clique mit Eingabe ?
Nichtdeterministische Laufzeit
Eine nichtdeterministische Turingmaschine darf in einer Situation mehrere Übergänge haben. Ihre Berechnungen auf einer Eingabe bilden deshalb einen Baum. Wir sagen, entscheidet in Zeit , wenn auf jeder Eingabe jeder Berechnungspfad nach höchstens Schritten hält und gilt: genau dann, wenn mindestens ein Pfad akzeptiert.
ist die Menge dieser Sprachen bei Laufzeit . Der Name NP steht für nichtdeterministisch polynomiell:
Zertifikate und Nichtdeterminismus sind gleichwertig
Eine Sprache hat genau dann einen Polynomialzeit-Verifizierer, wenn eine nichtdeterministische Turingmaschine sie in Polynomialzeit entscheidet. Die beiden Beschreibungen von NP ergeben also dieselbe Klasse.
Vom Verifizierer zur Maschine. Sei ein Verifizierer mit Laufzeit und Zertifikatsschranke . Die nichtdeterministische Maschine schreibt auf eine Eingabe zuerst ein Wort der Länge höchstens auf das Band, wobei sie jedes Zeichen (oder das Ende) nichtdeterministisch wählt. Dann rechnet sie deterministisch wie auf . Jeder Pfad hält nach Schritten und akzeptiert genau dann, wenn sein ein Zertifikat ist. Ein solches gibt es genau für .
Von der Maschine zum Verifizierer. Sei eine nichtdeterministische Maschine mit Laufzeit , und sei die größte Zahl von Übergängen, zwischen denen in einer Situation wählen kann. Ein Berechnungspfad ist durch die Folge seiner Wahlen festgelegt, also durch höchstens Zahlen aus . Diese Folge ist das Zertifikat, polynomiell lang, weil nicht von der Eingabe abhängt. Der Verifizierer simuliert auf entlang der Wahlen aus (passt eine Wahl nicht, lehnt er ab) und akzeptiert, wenn dieser Pfad akzeptiert. Genau für gibt es einen akzeptierenden Pfad und damit ein passendes .
P liegt in NP, NP liegt in EXP
Sei die Klasse der in Exponentialzeit entscheidbaren Sprachen. Dann gilt:
Erste Inklusion. Entscheidet die Sprache in Polynomialzeit, dann ist „ignoriere und rechne wie auf “ ein Polynomialzeit-Verifizierer; als Zertifikat genügt das leere Wort.
Zweite Inklusion. Sei ein Verifizierer für mit Laufzeit und Zertifikatsschranke . Eine deterministische Maschine startet der Reihe nach für alle mit und akzeptiert, sobald einmal akzeptiert. Über einem Alphabet mit Zeichen gibt es höchstens solche Wörter. Die Gesamtzeit liegt in für ein passendes . Insbesondere ist jede Sprache in NP entscheidbar.
Die Klasse co-NP
Das Komplement von ist . co-NP enthält alle Sprachen, deren Komplement in NP liegt; hier hat die Antwort nein kurze Zertifikate.
Beispiele sind UNSAT, die unerfüllbaren Formeln, und TAUT, die Formeln, die unter jeder Belegung wahr sind. Eine Belegung widerlegt die Unerfüllbarkeit; ob jede unerfüllbare Formel ein polynomiell langes, effizient prüfbares Zertifikat besitzt, ist offen.
Vertauscht man bei einem deterministischen Entscheider die Antwort, entscheidet er das Komplement. Also gilt . Ob gilt, ist offen.
Pseudopolynomialzeit beim Rucksack
Pseudopolynomialzeit beim Rucksack
Die Tabelle für das 0/1-Rucksackproblem hat Einträge und wird in Schritten gefüllt. Mit Wert gleich Gewicht und entscheidet sie auch Subset-Sum in .
Die Eingabe enthält aber binär. Mit Binärstellen kann bis zu groß sein, und die Tabelle hat dann Spalten. Die Laufzeit ist also polynomiell im Zahlenwert , aber exponentiell in der Länge dieser Zahl. Ein solches Verfahren heißt pseudopolynomiell.
| Kapazität | Binärstellen | Spalten der Tabelle |
|---|---|---|
Verdoppelt man die Stellenzahl von 20 auf 40, wächst die Tabelle um den Faktor eine Million. Bei unär kodierten Zahlen wäre das Verfahren polynomiell, denn dann ist schon die Eingabe etwa Zeichen lang. Pseudopolynomielle Verfahren helfen also bei kleinen Zahlen, beweisen aber nicht, dass Rucksack oder Subset-Sum in P liegen.
NP heißt nicht „nicht polynomiell“
NP heißt nicht „nicht polynomiell“
Ein verbreiteter Fehlschluss lautet: „NP sind die Probleme, die man nicht in Polynomialzeit lösen kann.“ Daraus folgt dann scheinbar, dass P und NP disjunkt sind und dass ein Problem in NP schwer sein muss.
NP steht für nichtdeterministisch polynomiell: Ja-Antworten haben kurze, effizient prüfbare Zertifikate. Jedes Problem aus P liegt auch in NP, zum Beispiel Erreichbarkeit oder der Primzahltest. Ob es in NP Probleme gibt, die nicht in P liegen, ist genau die offene Frage .
Zusammenfassung
Ein Entscheidungsproblem ist eine Sprache ; die Laufzeit misst man in der Länge der Kodierung, Zahlen werden binär geschrieben.
enthält die in deterministischer Polynomialzeit entscheidbaren Sprachen, etwa Erreichbarkeit und den Primzahltest.
Polynomialzeit ist robust gegenüber dem Rechenmodell, aber ist nicht praktisch, und der ungünstigste Fall ist nicht der typische.
NP enthält die Sprachen mit kurzen, in Polynomialzeit prüfbaren Zertifikaten, etwa SAT, Hamiltonkreis, Clique und Subset-Sum; gleichwertig entscheidet sie eine nichtdeterministische Maschine in Polynomialzeit.
; ob gilt, ist offen. co-NP enthält die Komplemente, etwa UNSAT.
Die Rucksacktabelle mit Schritten ist pseudopolynomiell: polynomiell im Zahlenwert , exponentiell in seiner Stellenzahl.
Übungen
Wie viele Zeichen hat die Binärdarstellung der Zahl ?
Welche Aussage ist nach heutigem Wissen bewiesen?
Subset-Sum mit den Zahlen und Ziel : Wie viele verschiedene Teilmengen dieser sechs Zahlen sind Zertifikate, haben also genau die Summe 9?
Ein Verfahren für Subset-Sum braucht Schritte. Was folgt daraus?
Die Sprache INDEPENDENT-SET enthält alle , für die der Graph eine unabhängige Menge der Größe hat, also Knoten, von denen keine zwei durch eine Kante verbunden sind. Zeige, dass INDEPENDENT-SET in NP liegt: Gib Zertifikat und Verifizierer an, schätze die Laufzeit ab und begründe beide Richtungen der Definition.
Zeige: Ist , dann ist .