Lektion 4.1

Die Klassen P und NP

45 min Lesezeit
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 26=642^6 = 64 Teilmengen, 60 Pakete schon 2602^{60}. 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.

Vermute zuerst

Ein Rechner prüft 10910^9 Teilmengen pro Sekunde. Wie lange braucht er ungefähr, um alle 2602^{60} Teilmengen von 60 Paketen durchzugehen?

Definition

Entscheidungsproblem und Kodierung

Ein Alphabet Σ\Sigma ist eine endliche, nicht leere Menge von Zeichen, meist Σ={0,1}\Sigma = \{0, 1\}. Σ∗\Sigma^* ist die Menge aller endlichen Wörter über Σ\Sigma, und ∣w∣|w| ist die Länge des Wortes ww.

Ein Entscheidungsproblem ist eine Frage, deren Antwort nur „ja“ oder „nein“ ist. Jede Eingabe (eine Instanz) schreiben wir als Wort ⟨x⟩∈Σ∗\langle x \rangle \in \Sigma^*, die Kodierung von xx. Das Problem ist dann die Sprache der Ja-Instanzen:

L={⟨x⟩∣die Antwort fu¨r x ist ja}⊆Σ∗L = \{\langle x \rangle \mid \text{die Antwort für } x \text{ ist ja}\} \subseteq \Sigma^*.

Das Problem lösen heißt, LL zu entscheiden: Eine Turingmaschine hält bei jeder Eingabe ww und akzeptiert genau dann, wenn w∈Lw \in L. Die Laufzeit messen wir in der Eingabelänge n=∣w∣n = |w|.

Beispiel

Wie lang ist eine Eingabe?

ObjektKodierungLänge
Zahl 10001000, binär111110100011111010001010
Zahl 10001000, unärtausend Einsen10001000
Zahl N≥1N \ge 1, binärBinärdarstellung⌊log⁡2N⌋+1\lfloor \log_2 N \rfloor + 1
Graph mit kk KnotenAdjazenzmatrix Zeile für Zeilek2k^2
Subset-Sum mit nn Zahlen bis BBalle Zahlen binär, durch Trennzeichen getrenntetwa nlog⁡2Bn \log_2 B

Die Adjazenzmatrix eines Graphen hat in Zeile ii, Spalte jj eine 11, wenn es eine Kante zwischen Knoten ii und Knoten jj gibt, sonst eine 00.

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

Definition

Laufzeit einer Turingmaschine und die Klasse P

Sei MM eine deterministische Turingmaschine, die bei jeder Eingabe hält. Ihre Laufzeit tM(n)t_M(n) ist die größte Zahl von Schritten, die MM auf einer Eingabe der Länge nn macht (der ungünstigste Fall).

TIME(t(n))\mathrm{TIME}(t(n)) ist die Menge der Sprachen, die eine deterministische Turingmaschine mit Laufzeit O(t(n))O(t(n)) entscheidet. Die Klasse P besteht aus allen Sprachen, die in Polynomialzeit entscheidbar sind, also in Zeit O(nk)O(n^k) für eine feste Zahl kk:

P=⋃k≥1TIME(nk)\mathrm{P} = \bigcup_{k \ge 1} \mathrm{TIME}(n^k)
Beispiel

Probleme in P

  • Erreichbarkeit: Gibt es einen Weg von ss nach tt? Breitensuche, O(k+m)O(k + m) bei kk Knoten und mm 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 ss nach tt mit Gewicht höchstens gg? Bei nichtnegativen Kantengewichten Dijkstra, polynomiell auch in der Länge der binär geschriebenen Gewichte.
  • Primzahltest: Ist die binär gegebene Zahl NN 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 gg in die Eingabe aufnimmt. Den optimalen Wert findet man dann meist durch binäre Suche über gg.

Kurz geprüft

Der Test „Teile NN durch alle Zahlen von 2 bis N\sqrt{N}“ braucht etwa N\sqrt{N} Divisionen. Ist er ein Polynomialzeit-Verfahren für den Primzahltest?

Satz

Robustheit von P

Entscheidet eine Turingmaschine mit mehreren Bändern eine Sprache in Zeit t(n)≥nt(n) \ge n, dann entscheidet eine Turingmaschine mit einem Band sie in Zeit O(t(n)2)O(t(n)^2). Ebenso simulieren Turingmaschinen die üblichen Rechnermodelle mit wahlfreiem Speicherzugriff (wenn eine Operation auf bb-Bit-Zahlen etwa bb Schritte kostet) mit polynomiellem Mehraufwand. P hängt deshalb nicht vom gewählten Modell ab.

Definition

Verifizierer und die Klasse NP

Ein Verifizierer für eine Sprache LL ist eine deterministische Turingmaschine VV, die Paare ⟨w,c⟩\langle w, c \rangle liest und bei jeder Eingabe hält. Das zweite Wort cc heißt Zertifikat (oder Zeuge). Es gilt:

w∈L  ⟺  w \in L \iff es gibt ein cc mit ∣c∣≤p(∣w∣)|c| \le p(|w|), sodass VV das Paar ⟨w,c⟩\langle w, c \rangle akzeptiert.

Dabei ist pp ein Polynom. Die Klasse NP besteht aus allen Sprachen, die einen Verifizierer mit Laufzeit polynomiell in ∣w∣|w| besitzen.

Für jedes w∈Lw \in L muss es ein passendes Zertifikat geben, für w∉Lw \notin L darf keines funktionieren, wie geschickt es auch gewählt ist.

Beispiel

Vier Probleme in NP

  • SAT: Ist eine aussagenlogische Formel φ\varphi erfüllbar, gibt es also eine Belegung der Variablen mit wahr und falsch, unter der φ\varphi wahr ist?
  • Hamiltonkreis: Hat ein ungerichteter Graph einen Kreis, der jeden Knoten genau einmal besucht?
  • Clique: Hat ein Graph GG eine Clique der Größe kk, also kk Knoten, die paarweise durch Kanten verbunden sind?
  • Subset-Sum: Gibt es zu natürlichen Zahlen a1,…,ana_1, \dots, a_n und einem Ziel TT eine Teilmenge der Indizes, deren Zahlen sich genau zu TT summieren?
ProblemZertifikatPrüfung
SATeine Belegung der Variablenφ\varphi auswerten, linear in der Formellänge
Hamiltonkreiseine Reihenfolge der Knotenjeder Knoten einmal, Nachbarn in der Folge benachbart
Cliqueeine Menge von kk Knotenalle (k2)\binom{k}{2} Paare in der Adjazenzmatrix nachsehen
Subset-Sumeine Teilmenge der Indizesdie ausgewählten Zahlen binär addieren und mit TT vergleichen

Jedes Zertifikat ist polynomiell lang, jede Prüfung polynomiell, also liegen alle vier Probleme in NP. Für das Paketproblem vom Anfang sind {4,5}\{4, 5\} und {3,4,2}\{3, 4, 2\} Zertifikate.

Beispiel

Ein Verifizierer für Hamiltonkreis

Die Eingabe ist ein Graph mit Knoten 1,…,k1, \dots, k als Adjazenzmatrix AA, das Zertifikat eine Folge v[1],…,v[k]v[1], \dots, v[k] von Knotennummern.

ZeileEinrückungAnweisung
10verify(A, v[1..k]):\texttt{verify(A, v[1..k]):}
21if k < 3: return false\texttt{if k < 3: return false}
31seen = [false] * k\texttt{seen = [false] * k}
41for i = 1 to k:\texttt{for i = 1 to k:}
52if v[i] < 1 or v[i] > k or seen[v[i]]: return false\texttt{if v[i] < 1 or v[i] > k or seen[v[i]]: return false}
62seen[v[i]] = true\texttt{seen[v[i]] = true}
71for i = 1 to k:\texttt{for i = 1 to k:}
82j = i + 1 if i < k else 1\texttt{j = i + 1 if i < k else 1}
92if A[v[i]][v[j]] == 0: return false\texttt{if A[v[i]][v[j]] == 0: return false}
101return true\texttt{return true}

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 kk Kanten des Kreises einschließlich der Rückkante von v[k]v[k] zu v[1]v[1].

Das sind O(k)O(k) 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.

Kurz geprüft

Welches Zertifikat eignet sich für Clique mit Eingabe ⟨G,k⟩\langle G, k \rangle?

Definition

Nichtdeterministische Laufzeit

Eine nichtdeterministische Turingmaschine NN darf in einer Situation mehrere Übergänge haben. Ihre Berechnungen auf einer Eingabe bilden deshalb einen Baum. Wir sagen, NN entscheidet LL in Zeit t(n)t(n), wenn auf jeder Eingabe ww jeder Berechnungspfad nach höchstens t(∣w∣)t(|w|) Schritten hält und gilt: w∈Lw \in L genau dann, wenn mindestens ein Pfad akzeptiert.

NTIME(t(n))\mathrm{NTIME}(t(n)) ist die Menge dieser Sprachen bei Laufzeit O(t(n))O(t(n)). Der Name NP steht für nichtdeterministisch polynomiell:

NP=⋃k≥1NTIME(nk)\mathrm{NP} = \bigcup_{k \ge 1} \mathrm{NTIME}(n^k)
Satz

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.

Satz

P liegt in NP, NP liegt in EXP

Sei EXP=⋃k≥1TIME(2nk)\mathrm{EXP} = \bigcup_{k \ge 1} \mathrm{TIME}(2^{n^k}) die Klasse der in Exponentialzeit entscheidbaren Sprachen. Dann gilt:

P⊆NP⊆EXP\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{EXP}
Definition

Die Klasse co-NP

Das Komplement von L⊆Σ∗L \subseteq \Sigma^* ist L‾=Σ∗∖L\overline{L} = \Sigma^* \setminus L. 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 P⊆NP∩co-NP\mathrm{P} \subseteq \mathrm{NP} \cap \text{co-NP}. Ob NP=co-NP\mathrm{NP} = \text{co-NP} gilt, ist offen.

Beispiel

Pseudopolynomialzeit beim Rucksack

Die Tabelle für das 0/1-Rucksackproblem hat (n+1)(W+1)(n+1)(W+1) Einträge und wird in O(nW)O(nW) Schritten gefüllt. Mit Wert gleich Gewicht und W=TW = T entscheidet sie auch Subset-Sum in O(nT)O(nT).

Die Eingabe enthält WW aber binär. Mit bb Binärstellen kann WW bis zu 2b−12^b - 1 groß sein, und die Tabelle hat dann 2b2^b Spalten. Die Laufzeit ist also polynomiell im Zahlenwert WW, aber exponentiell in der Länge bb dieser Zahl. Ein solches Verfahren heißt pseudopolynomiell.

Kapazität WWBinärstellenSpalten der Tabelle
10001000101010011001
10610^6202010000011000001
101210^{12}40401012+110^{12} + 1

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 WW Zeichen lang. Pseudopolynomielle Verfahren helfen also bei kleinen Zahlen, beweisen aber nicht, dass Rucksack oder Subset-Sum in P liegen.

Häufige Fehler

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.

Richtig ist

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 P=NP\mathrm{P} = \mathrm{NP}.

Zusammenfassung

  • Ein Entscheidungsproblem ist eine Sprache L⊆Σ∗L \subseteq \Sigma^*; die Laufzeit misst man in der Länge der Kodierung, Zahlen werden binär geschrieben.

  • P=⋃kTIME(nk)\mathrm{P} = \bigcup_k \mathrm{TIME}(n^k) enthält die in deterministischer Polynomialzeit entscheidbaren Sprachen, etwa Erreichbarkeit und den Primzahltest.

  • Polynomialzeit ist robust gegenüber dem Rechenmodell, aber n100n^{100} 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.

  • P⊆NP⊆EXP\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{EXP}; ob P=NP\mathrm{P} = \mathrm{NP} gilt, ist offen. co-NP enthält die Komplemente, etwa UNSAT.

  • Die Rucksacktabelle mit O(nW)O(nW) Schritten ist pseudopolynomiell: polynomiell im Zahlenwert WW, exponentiell in seiner Stellenzahl.

Übungen

Aufgabe 1Numerisch

Wie viele Zeichen hat die Binärdarstellung der Zahl 50005000?

Aufgabe 2Multiple Choice

Welche Aussage ist nach heutigem Wissen bewiesen?

Aufgabe 3Numerisch

Subset-Sum mit den Zahlen 3,34,4,12,5,23, 34, 4, 12, 5, 2 und Ziel T=9T = 9: Wie viele verschiedene Teilmengen dieser sechs Zahlen sind Zertifikate, haben also genau die Summe 9?

Aufgabe 4Multiple Choice

Ein Verfahren für Subset-Sum braucht O(n⋅T)O(n \cdot T) Schritte. Was folgt daraus?

Aufgabe 5Freitext

Die Sprache INDEPENDENT-SET enthält alle ⟨G,k⟩\langle G, k \rangle, für die der Graph GG eine unabhängige Menge der Größe kk hat, also kk 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.

Aufgabe 6Freitext

Zeige: Ist P=NP\mathrm{P} = \mathrm{NP}, dann ist NP=co-NP\mathrm{NP} = \text{co-NP}.