In der rechenbetonten Kompliziertheitstheorie ist NP eine der grundsätzlichsten Kompliziertheitsklassen.

Die Abkürzung NP bezieht sich auf die "nichtdeterministische polynomische Zeit."

Intuitiv ist NP der Satz aller Entscheidungsprobleme, für die die Beispiele wo die Antwort "ja" ist, haben effizient nachprüfbare Beweise der Tatsache, dass die Antwort tatsächlich "ja" ist. Genauer müssen diese Beweise in der polynomischen Zeit durch eine deterministische Maschine von Turing nachprüfbar sein.

In einer gleichwertigen formellen Definition ist NP der Satz von Entscheidungsproblemen, wo "ja" - Beispiele in der polynomischen Zeit durch eine nichtdeterministische Maschine von Turing entschieden werden können. Die Gleichwertigkeit der zwei Definitionen folgt aus der Tatsache, dass ein Algorithmus auf solch einer nichtdeterministischen Maschine aus zwei Phasen besteht, von denen die erste aus einer Annahme über die Lösung besteht, die auf eine nichtdeterministische Weise erzeugt wird, während das zweite aus einem deterministischen Algorithmus besteht, der nachprüft oder die Annahme als eine gültige Lösung des Problems zurückweist.

Die Kompliziertheitsklasse P wird in NP enthalten, aber NP enthält viele wichtige Probleme, von denen das härteste NP-complete Probleme genannt werden, für die keine polynomisch-maligen Algorithmen bekannt sind, um sie zu lösen (obwohl sie in der polynomischen Zeit nachgeprüft werden können). Die wichtigste geöffnete Frage in der Kompliziertheitstheorie, der P = NP Problem, fragt, ob solche Algorithmen wirklich für NP-complete, und durch die Folgeerscheinung, alle NP Probleme bestehen. Es wird weit geglaubt, dass das nicht der Fall ist.

Formelle Definition

Die Kompliziertheitsklasse NP kann in Bezug auf NTIME wie folgt definiert werden:

Wechselweise kann NP mit deterministischen Maschinen von Turing als verifiers definiert werden. Eine Sprache L ist in NP, wenn, und nur wenn dort Polynome p und q und eine deterministische Maschine von Turing M, solch dass bestehen

• Für den ganzen x und y, die Maschine M Läufe rechtzeitig p (x) auf dem Eingang (x, y)
• Für den ganzen x in L, dort besteht eine Schnur y von der Länge q (x) solch dass M (x, y) = 1
• Für den ganzen x nicht in L und alle Schnuren y der Länge q (x), M (x, y) = 0

Einführung

Viele natürliche Informatik-Probleme werden durch die Klasse NP bedeckt.

Insbesondere die Entscheidungsversionen von vielen interessanten Suchproblemen und Optimierungsproblemen werden in NP enthalten.

Mit Sitz in Verifier Definition

Um die mit Sitz in verifier Definition von NP zu erklären, lassen Sie uns das Teilmenge-Summe-Problem denken:

Nehmen Sie an, dass uns einige ganze Zahlen, solcher als {7, 3, 2, 5, 8} gegeben werden, und wir wissen möchten, ob einige dieser ganzen Zahlen zur Null summieren. In diesem Beispiel ist die Antwort "ja", da die Teilmenge von ganzen Zahlen {3, 2, 5} der Summe Die Aufgabe des Entscheidens entspricht, ob solch eine Teilmenge mit der Summe-Null besteht, wird das Teilmenge-Summe-Problem genannt.

Weil die Zahl von ganzen Zahlen, die wir in den Algorithmus füttern, größer wird, wächst die Zahl von Teilmengen exponential, und tatsächlich ist das Teilmenge-Summe-Problem NP-complete.

Bemerken Sie jedoch, dass, wenn uns eine besondere Teilmenge gegeben wird (hat häufig ein Zertifikat genannt), wir leicht überprüfen oder nachprüfen können, ob die Teilmenge-Summe Null ist, indem sie gerade die ganzen Zahlen der Teilmenge summiert wird. So, wenn die Summe tatsächlich Null ist, dass besondere Teilmenge der Beweis oder Zeuge für die Tatsache ist, dass die Antwort "ja" ist. Ein Algorithmus, der nachprüft, ob eine gegebene Teilmenge Summe-Null hat, wird verifier genannt. Wie man sagt, ist ein Problem in NP, wenn, und nur wenn dort ein verifier für das Problem besteht, das in der polynomischen Zeit durchführt. Im Falle des Teilmenge-Summe-Problems braucht der verifier nur polynomische Zeit, für den Grund das Teilmenge-Summe-Problem in NP ist.

Bemerken Sie, dass die mit Sitz in verifier Definition von NP kein easy-verify Zertifikat für "nein" - Antworten verlangt. Die Klasse von Problemen mit solchen Zertifikaten für "nein" - Antworten wird co-NP genannt. Tatsächlich ist es eine geöffnete Frage, ob alle Probleme in NP auch Zertifikate für "nein" - Antworten haben und so in co-NP sind.

Maschinendefinition

Gleichwertig zur mit Sitz in verifier Definition ist die folgende Charakterisierung: NP ist der Satz von Entscheidungsproblemen, die durch eine nichtdeterministische Maschine von Turing entscheidbar sind, die in der polynomischen Zeit läuft. (Das bedeutet, dass es einen akzeptierenden Berechnungspfad iff gibt, ist ein Wort auf der Sprache - co-NP wird Doppel-mit der Zurückweisung von Pfaden definiert.) Ist diese Definition zur mit Sitz in verifier Definition gleichwertig, weil eine nichtdeterministische Maschine von Turing ein NP Problem in der polynomischen Zeit beheben konnte, indem sie ein Zertifikat nichtdeterministisch ausgewählt worden ist und den verifier auf dem Zertifikat geführt worden ist. Ähnlich, wenn solch eine Maschine besteht, dann kann eine polynomische Zeit verifier davon natürlich gebaut werden.

Beispiele

Das ist eine unvollständige Liste von Problemen, die in NP sind.

• Alle Probleme in P (Da gegeben ein Zertifikat für ein Problem in P, wir können das Zertifikat ignorieren und gerade das Problem in der polynomischen Zeit beheben. Bemerken Sie wechselweise, dass eine deterministische Maschine von Turing auch trivial eine nichtdeterministische Maschine von Turing ist, die gerade zufällig jeden Nichtdeterminismus nicht verwendet.)
• Die Entscheidungsproblem-Version der ganzen Zahl factorization Problem: Gegebene ganze Zahlen n und k, ist dort ein Faktor f mit 1