NP (Komplexitätsklasse)

Grundidee und Bedeutung

NP („nichtdeteterministisch polynomielle Zeit“) ist eine grundlegende Komplexitätsklasse der Informatik. Sie enthält Entscheidungsprobleme, also Probleme mit einer „Ja“- oder „Nein“-Antwort, bei denen sich ein Beweis für eine „Ja“-Antwort in Polynomialzeit überprüfen lässt. Polynomialzeit bedeutet, dass die benötigte Rechenzeit durch ein Polynom in der Eingabelänge beschränkt ist. Das Finden eines solchen Beweises kann dennoch sehr aufwendig sein.

Gleichwertig kann NP als die Klasse der Entscheidungsprobleme beschrieben werden, die eine nichtdeterministische Turingmaschine (NTM) in Polynomialzeit löst. Eine NTM kann verschiedene Rechenzweige verfolgen. Eine Eingabe wird akzeptiert, wenn mindestens einer dieser Zweige einen passenden Beweis findet und erfolgreich überprüft.

NP bedeutet nicht „nicht in Polynomialzeit lösbar“. NP legt nur eine obere Schranke fest und enthält insbesondere alle Probleme aus P, also alle Probleme, die eine deterministische Turingmaschine in Polynomialzeit lösen kann. Daher gilt P ⊆ NP.

Besonders wichtig sind NP-vollständige Probleme. Sie liegen selbst in NP, und jedes andere Problem aus NP kann polynomiell auf sie reduziert werden. In diesem Sinn sind sie die schwierigsten Probleme in NP. Für sie sind keine deterministischen Algorithmen bekannt, die alle Probleminstanzen in Polynomialzeit lösen; die bekannten Algorithmen benötigen im schlechtesten Fall exponentiellen Rechenaufwand. Ob dennoch ein Polynomialzeitalgorithmus existiert, ist Gegenstand des P-NP-Problems.

Formale Definitionen

Nach der Sprachakzeptanz-Definition liegt eine Sprache L in NP, wenn eine nichtdeterministische Turingmaschine M und ein Polynom p existieren, sodass zwei Bedingungen gelten:

• Bei Eingabe x hält jeder Lauf von M nach höchstens p(|x|) Schritten.

• x ∈ L gilt genau dann, wenn mindestens ein akzeptierender Lauf von M auf x existiert.

Dabei bezeichnet |x| die Länge der Eingabe. Anders ausgedrückt besitzt L einen polynomiell laufzeitbeschränkten Verifikator M mit L(M) = L.

Nach der Suchproblem-Definition liegt L in NP, wenn eine Relation R_L ⊆ {0,1}* × {0,1}* und ein Polynom p existieren, sodass R_L von einer deterministischen, polynomiell zeitbeschränkten Turingmaschine erkannt wird und gilt:

x ∈ L genau dann, wenn ein y mit |y| ≤ p(|x|) und (x,y) ∈ R_L existiert.

Das Wort y heißt Zertifikat von x. Wenn x tatsächlich zu L gehört, nennt man y auch „Beweis“ (proof) oder „Zeuge“ (witness); R_L wird deshalb auch witness relation genannt.

Gleichwertigkeit und weitere Charakterisierung

Die beiden formalen Definitionen sind äquivalent. Erkennt eine NTM M die Sprache L, dann gibt es für jedes x ∈ L eine akzeptierende Rechnung von M. Diese lässt sich als String α_M(x) kodieren. Da die Rechnung polynomial in |x| beschränkt ist, kann sie eine deterministische Maschine in Polynomialzeit überprüfen. Sie dient somit als Zertifikat in der Relation R_L.

Existiert umgekehrt eine geeignete Relation R_L, kann eine NTM ein Wort y nichtdeterministisch raten und anschließend mit einer deterministischen Turingmaschine prüfen, ob (x,y) ∈ R_L gilt. Damit akzeptiert sie genau die Eingaben x ∈ L.

Eine weitere gleichwertige Charakterisierung stammt aus der deskriptiven Komplexitätstheorie: Nach dem Satz von Fagin liegt eine Sprache L genau dann in NP, wenn es einen Satz der existenziellen Prädikatenlogik zweiter Stufe (SO∃) gibt, der L beschreibt.

Beziehungen und Eigenschaften

Co-NP bezeichnet die Klasse der Entscheidungsprobleme, deren Komplemente in NP liegen. NP und Co-NP sind nicht disjunkt, denn P ⊆ NP ∩ Co-NP. Ob NP = Co-NP gilt, ist unbekannt. Aus P = NP würde diese Gleichheit folgen, weil P unter Komplementbildung abgeschlossen ist.

Für zahlreiche Komplexitätsklassen kennt man nur Inklusionen, nicht aber in jedem Fall, ob sie echt sind:

L ⊆ NL ⊆ LOGCFL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE = NEXPSPACE.

Als echte Inklusionen sind unter anderem LOGCFL ⊂ PSPACE, P ⊂ EXPTIME, PSPACE ⊂ EXPSPACE und Q ⊂ NP bekannt.

NP ist abgeschlossen unter Vereinigung, Durchschnitt, Konkatenation, Kleene-Stern, epsilon-freien Homomorphismen und inversen Homomorphismen. „Abgeschlossen“ bedeutet hier, dass die jeweilige Operation auf Sprachen aus NP wieder eine Sprache aus NP ergibt.

Ungeklärt sind insbesondere die Fragen NP ⊆ P, PSPACE ⊆ NP, EXPTIME ⊆ NP, NP ⊆ Co-NP und Co-NP ⊆ NP. Die erste Frage ist das P-NP-Problem und zählt zu den wichtigsten offenen Problemen der Informatik.

Typische Probleme

Zu den bekannten NP-vollständigen Problemen gehören SAT, das Cliquenproblem, das Hamiltonkreisproblem, das Rucksackproblem, Independent Set, CSAT, 3-SAT, NODE-COVER und das Problem des Handlungsreisenden; außerdem werden Karps 21 NP-vollständige Probleme als wichtige Gruppe genannt.

Beim Problem des Handlungsreisenden fragt die Entscheidungsversion, ob durch gegebene Städte eine Rundreise existiert, deren Länge eine vorgegebene Grenze nicht überschreitet.

Alle Probleme aus P gehören ebenfalls zu NP, weil sich aus jeder deterministischen Turingmaschine eine äquivalente nichtdeterministische Turingmaschine konstruieren lässt. Auch das Graphisomorphieproblem – die Frage, ob zwei Graphen zueinander isomorph sind – liegt in NP. Es ist jedoch nicht bekannt, ob es NP-vollständig ist.