NP (Komplexität)

Euler -Diagramm zum P, NP, NP-Complete, und Np-harte Probleme. Unter der Annahme, dass p ≠ np die Existenz von Problemen innerhalb von NP, aber außerhalb beide P und NP-Complete war Gegründet von Ladner.^[1]

Im Computerkomplexitätstheorie, Np (Nichtdeterministische Polynomzeit) ist ein Komplexitätsklasse verwendet, um zu klassifizieren Entscheidungsprobleme. NP ist das einstellen von Entscheidungsproblemen, für die die Probleminstanzen, wo die Antwort "Ja" ist, haben Beweise Überprüfbar in Polynomzeit durch eine deterministische Turing -Maschineoder alternativ die Reihe von Problemen, die in Polynomzeit durch a gelöst werden können Nichtdeterministische Turing -Maschine.^{[2][Anmerkung 1]}

Eine äquivalente Definition von NP ist die Reihe von Entscheidungsproblemen lösbar in der Polynomzeit von a Nichtdeterministische Turing -Maschine. Diese Definition ist die Grundlage für die Abkürzung NP; "Nichtdeterministisch, Polynomzeit. "Diese beiden Definitionen sind äquivalent, da der auf der Turing -Maschine basierende Algorithmus aus zwei Phasen besteht Deterministischer Algorithmus, der überprüft, ob die Vermutung eine Lösung für das Problem ist.^[3]

Es ist leicht zu erkennen, dass die Komplexitätsklasse P (Alle Probleme lösbar, deterministisch, in Polynomzeit) sind in NP enthalten (Probleme, bei denen Lösungen in der Polynomzeit verifiziert werden können), denn wenn ein Problem in der Polynomzeit lösbar ist . Aber NP enthält viele weitere Probleme,^{[Anmerkung 2]} die härtesten werden genannt NP-Complete Probleme. Ein Algorithmus, der ein solches Problem in der Polynomzeit löst, kann auch jedes andere NP -Problem in der Polynomzeit lösen. Das wichtigste P gegen np ("p = np?") Problem, fragt, ob Polynomzeitalgorithmen zur Lösung von NP-Complete und bei Korollar alle NP-Probleme existieren. Es wird allgemein angenommen, dass dies nicht der Fall ist.^[4]

Die Komplexitätsklasse NP hängt mit der Komplexitätsklasse zusammen Co-NP für die die Antwort "Nein" in Polynomzeit verifiziert werden kann. Ob NP = Co-NP eine weitere herausragende Frage in der Komplexitätstheorie ist oder nicht.^[5]

Formale Definition

Die Komplexitätsklasse NP kann in Bezug auf definiert werden Ntzeit folgendermaßen:

$oder$

wo ${\ displayStyle {\ mathsf {ntime}} (n^{k})}$ ist die Reihe von Entscheidungsproblemen, die von a gelöst werden können Nichtdeterministische Turing -Maschine in ${\ displayStyle o (n^{k})}$ Zeit.

Alternativ kann NP unter Verwendung deterministischer Turing -Maschinen als Verifizierer definiert werden. EIN Sprache L ist in NP, wenn und nur wenn es Polynome gibt p und qund eine deterministische Turing -Maschine M, so dass

• Für alle x und y, Die Maschine M läuft rechtzeitig p(|x|) beim Eingang ${\ displayStyle (x, y)}$
• Für alle x in LEs gibt eine Schnur y von Länge q(|x|) so dass ${\ displayStyle m (x, y) = 1}$
• Für alle x nicht in L und alle Saiten y von Länge q(|x|),, ${\ displayStyle m (x, y) = 0}$

Hintergrund

Viele Informatik Probleme sind in NP enthalten, wie Entscheidungsversionen von vielen Suche und Optimierungsprobleme.

Verifier-basierte Definition

Betrachten Sie die auf nach auf Verifikern basierende Definition von NP erkläre die Betrachtung der Summenproblem: Angenommen, wir erhalten etwas Ganzzahlen, {–7, –3, –2, 5, 8}, und wir möchten wissen, ob einige dieser Ganzzahlen bis zu Null betragen. Hier lautet die Antwort "Ja", da die Ganzzahlen {–3, –2, 5} der Summe entsprechen (–3) + (–2) + 5 = 0.

Um zu antworten, wenn einige der Ganzzahlen auf Null hinzufügen, können wir einen Algorithmus erstellen, der alle möglichen Teilmengen erhält. Wenn die Anzahl der Ganzzahlen, die wir in den Algorithmus einfügen, größer wird, wächst sowohl die Anzahl der Teilmengen als auch die Berechnungszeit exponentiell.

Beachten Sie jedoch, dass wir, wenn wir eine bestimmte Teilmenge erhalten, wir können effizient überprüfen ob die Teilmenge Summe Null ist, indem die Ganzzahlen der Teilmenge summiert werden. Wenn die Summe Null ist, ist diese Teilmenge a nachweisen oder Zeuge Denn die Antwort lautet "Ja". Ein Algorithmus, der überprüft, ob eine bestimmte Untergruppe Summe Null hat Überprüfung. Das Summieren der Ganzzahlen einer Untergruppe kann eindeutig in der Polynomzeit erfolgen und das Problem der Untergruppe der Untergruppe ist daher in NP.

Das obige Beispiel kann für jedes Entscheidungsproblem verallgemeinert werden. Angesichts einer Instanz i von Problem ${\ displayStyle \ pi}$ und Zeuge W, wenn es eine gibt a Überprüfung V, so dass angesichts des geordneten Paares (i, w) als Eingabe in Polynomzeit "Ja" zurückgibt, wenn der Zeuge beweist, dass die Antwort in der Polynomzeit "Ja" oder "Nein" ist, anders, dann ${\ displayStyle \ pi}$ ist in NP.

Die "no" -Antan-Version dieses Problems wird angegeben als: "Hat jede nicht leere Untergruppe eine endliche Reihe von Ganzzahlen eine Summe ungleich Null?". Die auf auf Verifier basierende Definition von NP tut es nicht Erfordern Sie einen effizienten Prüfer für die "no" -Antrails. Die Klasse der Probleme mit solchen Überprüfern für die "NEIN" -Antrails wird als CO-NP bezeichnet. Tatsächlich ist es eine offene Frage, ob alle Probleme in NP auch Überprüfungen für die "Nein" -Antrikern haben und somit in Co-NP sind.

In einer Literatur wird der Verifier als "Zertifizierer" und der Zeuge des "genannt"Zertifikat".^[2]

Maschinendefinition

Äquivalent zur auf Verifizierer basierenden Definition ist die folgende Charakterisierung: NP ist die Klasse von Entscheidungsprobleme lösbar durch a Nichtdeterministische Turing -Maschine Das läuft herein Polynomzeit. Das heißt, ein Entscheidungsproblem ${\ displayStyle \ pi}$ ist in NP, wann immer ${\ displayStyle \ pi}$ wird durch eine polynomiale nicht deterministische Turing-Maschine erkannt ${\ displayStyle m}$ mit einem Existenzielle Akzeptanzbedingung, bedeutet, dass ${\ displayStyle w \ in \ pi}$ wenn und nur wenn ein Berechnungspfad von ${\ displayStyle m (w)}}$ führt zu einem akzeptierenden Staat. Diese Definition entspricht der auf Verifizierer basierenden Definition, da eine nichtdeterministische Turing-Maschine ein NP-Problem in der Polynomzeit durch Nichtdeterministisch ausgewählt und ein Zertifikat ausgewählt und den Überprüfer auf dem Zertifikat ausgeführt wird. Wenn eine solche Maschine existiert, kann ein Polynom -Zeit -Verifizierer natürlich daraus konstruiert werden.

In diesem Licht können wir Co-NP doppelt als die Klasse von Entscheidungsproblemen definieren, die durch polynomiale Zeit nicht-deterministische Turing-Maschinen mit einer existenziellen Ablehnungsbedingung erkennbar sind. Da eine existenzielle Ablehnungsbedingung genau dasselbe ist wie a Universelle Akzeptanzzustandwir können das verstehen NP vs. Co-NP Frage als Frage, ob die existenziellen und universellen Akzeptanzbedingungen die gleiche ausdrucksstarke Kraft für die Klasse der nicht deterministischen Turing-Maschinen der Polynomzeit haben.

Eigenschaften

NP ist unter geschlossen unter Union, Überschneidung, Verkettung, Kleene Star und Umkehrung. Es ist nicht bekannt, ob NP unter geschlossen ist ergänzen (Diese Frage ist die sogenannte Frage "NP gegen Co-NP"))

Warum einige NP -Probleme schwer zu lösen sind

Aufgrund der vielen wichtigen Probleme in dieser Klasse gab es umfangreiche Anstrengungen, um Polynom-Zeit-Algorithmen für Probleme in NP zu finden. Es bleibt jedoch eine große Anzahl von Problemen in NP, die solchen Versuchen trotzen und zu erfordern scheinen Superpolynomzeit. Ob diese Probleme in der Polynomzeit nicht lichtdurchschnittlich sind, ist eine der größten offenen Fragen in Informatik (sehen P Versus NP ("P = NP") Problem für eine eingehende Diskussion).

Ein wichtiger Begriff in diesem Zusammenhang ist der Satz von NP-Complete Entscheidungsprobleme, die eine Untergruppe von NP sind und möglicherweise informell als "härteste" Probleme in NP bezeichnet werden. Wenn es einen Polynom-Zeit-Algorithmus für sogar gibt eines Von ihnen gibt es dann einen Polynom-Zeit-Algorithmus für alle Die Probleme in NP. Aus diesem Grund hat sich dedizierte Forschungen nicht für ein Polynomalgorithmus für ein NP-Complete-Problem gefunden. Sobald sich ein Problem als NP-Complete erwiesen hat existieren.

In praktischen Verwendungen kann jedoch in der Polynomzeit häufig eine optimale Lösung suchen, anstatt Rechenressourcen zu suchen, anstatt nach einer optimalen Lösung zu suchen. Außerdem sind die realen Anwendungen einiger Probleme einfacher als ihre theoretischen Äquivalente.

Äquivalenz von Definitionen

Die beiden Definitionen von NP als die Klasse von Problemen, die durch einen Nichtdeterministik lösbar sind Turing Maschine . Der Beweis wird von vielen Lehrbüchern beschrieben, zum Beispiel SIPsers Introduction to the Theory of Computation, Abschnitt 7.3.

Um dies zu zeigen, nehmen wir zunächst an, wir haben einen deterministischen Prüfer. Eine nicht deterministische Maschine kann einfach nicht deterministisch den Verifizierer auf allen möglichen Beweisketten ausführen (dies erfordert nur polynomial viele Schritte ). Wenn ein Beweis gültig ist, wird ein Pfad akzeptiert; Wenn kein Beweis gültig ist, befindet sich die Zeichenfolge nicht in der Sprache und lehnt ab.

Angenommen, wir haben einen nicht deterministischen TM, der als Akzeptanz einer bestimmten Sprache L an jedem seiner polynomialen Schritte, der Maschine Berechnungsbaum Zweige in höchstens einer begrenzten Anzahl von Richtungen. Es muss mindestens einen akzeptierenden Pfad geben, und die Zeichenfolge, die diesen Pfad beschreibt, ist der Beweis, der dem Verifizierer geliefert wird. Der Verifizierer kann dann A deterministisch simulieren, wobei nur dem Akzeptanzpfad befolgt und die am Ende akzeptiert werden. Wenn ein Eingang abgelehnt wird, gibt es keinen Akzeptanzpfad, und der Überprüfer lehnt immer ab.

Beziehung zu anderen Klassen

NP enthält alle Probleme in P, da man jede Instanz des Problems überprüfen kann, indem man einfach den Beweis ignoriert und löst. NP ist in enthalten in PSPACE-Um dies zu zeigen, genügt es, eine PSPACE-Maschine zu konstruieren, die alle Beweisketten über einen Polynom-Zeit-Prüfer läuft. Da eine Polynomzeitmaschine nur viele Bits lesen kann, kann sie nicht mehr als Polynomraum verwenden, noch kann eine Proof-Zeichenfolge mehr als Polynomraum einnehmen (daher müssen wir keine längeren Beweise in Betracht ziehen). NP ist auch in enthalten NachfolgerDa der gleiche Algorithmus in Exponentialzeit arbeitet.

CO-NP enthält die Probleme, die einen einfachen Beweis für einen einfachen Beweis haben nein Instanzen, manchmal als Gegenbeispiele bezeichnet. Zum Beispiel, Primalitätstest Trivial liegt in CO-NP, da man die Primalität einer Ganzzahl widerlegen kann, indem man lediglich einen nicht trivialen Faktor liefert. NP und Co-NP zusammen bilden die erste Ebene in der Polynomhierarchie, nur höher als P.

NP wird nur mit deterministischen Maschinen definiert. Wenn wir es dem Verifizierer probabilistisch sein erlauben (dies ist jedoch nicht unbedingt eine BPP -Maschine^[6]), wir bekommen die Klasse Ma Lösbar mit einem Arthur -Merlin -Protokoll ohne Kommunikation von Arthur nach Merlin.

NP ist eine Klasse von Entscheidungsprobleme; Die analoge Klasse von Funktionsproblemen ist Fnp.

Die einzigen bekannten strengen Einschlüsse kommen von der Zeithierarchie Theorem und die Raumhierarchie Theoremund jeweils sind sie ${\ displaystyle {\ mathsf {np \ subsetneq nexptime}}}$ und ${\ displayStyle {\ mathsf {np \ subetneq Expace}}}$.

Andere Charakterisierungen

Bezüglich Beschreibende Komplexitätstheorie, NP entspricht genau dem von existentiell definierbaren Sprachen, der definierbar ist Logik zweiter Ordnung (Fagins Theorem).

NP kann als eine sehr einfache Art von gesehen werden Interaktives Proof -System, wo der Prover das Proof-Zertifikat und der Überprüfer ein deterministischer Polynomzeitmaschine ist, der es überprüft. Es ist vollständig, weil die richtige Proof -Zeichenfolge es akzeptiert, wenn es eine gibt, und es ist ein Ton, da der Verifier nicht akzeptieren kann, wenn es keine akzeptable Beweiszeichenfolge gibt.

Ein wichtiges Ergebnis der Komplexitätstheorie ist, dass NP als die Probleme charakterisiert werden kann Probabilistisch prüfbare Beweise wo der Verifizierer o (log n) Zufällige Bits und untersucht nur eine konstante Anzahl von Bits der Proof -Zeichenfolge (die Klasse PCP(Protokoll n1)). Informell besser bedeutet dies, dass der oben beschriebene NP-Verifikator durch einen ersetzt werden kann, der nur einige Stellen in der Proof-Zeichenfolge "feststellen", und die Verwendung einer begrenzten Anzahl von Münzflips kann die richtige Antwort mit hoher Wahrscheinlichkeit bestimmen. Dies ermöglicht mehrere Ergebnisse über die Härte von Näherungsalgorithmen bewiesen sein.

Beispiele

Dies ist eine Liste mit einigen Problemen, die in NP sind:

Alle Probleme in P, bezeichnet ${\ displayStyle {\ mathsf {p \ subseteq np}}}$. Ein Zertifikat für ein Problem in PWir können das Zertifikat ignorieren und das Problem in der Polynomzeit lösen.

Die Entscheidungsversion der Problem mit reisenden Verkäufern ist in NP. Bei einer Eingangsmatrix von Abständen zwischen n Städte, das Problem besteht darin, festzustellen, ob eine Route vorhanden ist, die alle Städte mit einer Gesamtentfernung weniger als besucht k.

Ein Beweis kann einfach eine Liste der Städte sein. Anschließend kann die Überprüfung eindeutig in Polynomzeit durchgeführt werden. Es fügt einfach die Matrixeinträge hinzu, die den Pfaden zwischen den Städten entsprechen.

A Nichtdeterministische Turing -Maschine kann eine solche Route wie folgt finden:

• In jeder Stadt besucht es die nächste Stadt, bis sie jeden Scheitelpunkt besucht hat. Wenn es stecken bleibt, stoppt es sofort.
• Am Ende überprüft es, dass die Route, die sie entschieden hat, weniger gekostet hat als k in O(n) Zeit.

Man kann jede Vermutung als "vorstellen"Gabel"Eine neue Kopie der Turing -Maschine, um jedem der möglichen Pfade nach vorne zu folgen, und wenn mindestens eine Maschine einen Entfernungsweg weniger findet als kDiese Maschine akzeptiert den Eingang. (Äquivalent kann dies als eine einzelne Turing -Maschine betrachtet werden, die immer richtig erraten)

A binäre Suche Über den Bereich möglicher Entfernungen können die Entscheidungsversion von reisenden Verkäufern in die Optimierungsversion umwandeln, indem die Entscheidungsversion wiederholt aufgerufen wird (eine Polynom Anzahl).^[7][8]

Die Entscheidungsproblemversion der Ganzzahlfaktorisierungsproblem: Ganzzahlen gegeben n und k, gibt es einen Faktor? f mit 1 < f < k und f dividieren n?^[8]

Das Problem mit Subgraphisomorphismus zu bestimmen, ob Grafik G Enthält einen Untergraphen, der isomorph ist, um darzustellen H.^[9]

Das Boolesche Zufriedenheitsproblem, wo wir wissen wollen, ob eine bestimmte Formel in Aussagelogik Bei booleschen Variablen gilt für einen Wert der Variablen.^[10]

Siehe auch

• Turing Maschine

Anmerkungen

Verweise

Weitere Lektüre

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, und Clifford Stein. Einführung in Algorithmen, Zweite Ausgabe. MIT Press und McGraw-Hill, 2001. ISBN0-262-03293-7. Abschnitt 34.2: Polynomzeitüberprüfung, S. 979–983.
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-x. Abschnitte 7.3–7.5 (Klasse NP, NP-Vervollständigung, zusätzliche Probleme mit NP-Vervollständigung), S. 241–271.
• David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3. Auflage, 2004.

Externe Links

• Komplexitätszoo: Np
• Amerikanischer Wissenschaftler Grundierung zur traditionellen und neueren Komplexitätstheorieforschung: "Zufällige Algorithmen"