WikiDer > NP (Komplexitätsklasse)

NP (complexiteitsklasse)
Übersicht über P, NP und NP-vollständig, sofern P ungleich NP ist.

NP, die Bezeichnung für nichtdeterministisches Polynom, ist ein Komplexitätsklasse diese alle Entscheidungsprobleme enthält löslich in oplosbaar Polynomzeit durch eine nichtdeterministische Turingmaschine.

In dem Komplexitätstheorie ist NP auch bekannt als NZEIT( neinO(1) )

NP kann auch als Sammlung Entscheidungsprobleme (mit 'ja' oder 'nein' beantwortbar), für die eine 'ja'-Lösung in polynomieller Zeit durch a . verifiziert werden kann deterministische Turingmaschine. Zu den Entscheidungsproblemen, für die eine 'Nein'-Lösung leicht zu überprüfen ist, gehören Co-NP, das Komplement von NP.

Definition

NP kann definiert werden durch NZEIT:

.

1974, Ronald Fagin das Satz von Fagin bewiesen, dass ein Entscheidungsproblem in existenziellen Logik zweiter Ordnung kann ausgedrückt werden dann und nur dann, wenn es ist in polynomieller Zeit durch eine nichtdeterministische Turingmaschine lösbar (also gehört es zu NP). Ähnliche Sätze wurden seitdem auch für andere Komplexitätsklassen bewiesen.[1]

Eigenschaften

Die Komplexitätsklasse p ist ein Teilmenge aus NP; Eine nicht-deterministische Turing-Maschine, die keinen Nicht-Determinismus verwendet, ist äquivalent zu einer deterministischen Turing-Maschine. Die Entscheidungsprobleme in P gehören daher auch zu NP. Es wird vermutet, dass P a . ist strenge Teilmenge von NP.

NP enthält alle Entscheidungsprobleme, für die eine gegebene Lösung in polynomieller Zeit überprüft werden kann; dies schließt auch alle Entscheidungsprobleme aus P ein, da man den Lösungsvorschlag einfach ignorieren und das Problem in polynomieller Zeit lösen kann.

NP-Vollständigkeit

sehen NP-vollständig für den Hauptartikel zu diesem Thema.

Alle NP-vollständigen Probleme gehören per Definition zu NP: Ein Entscheidungsproblem ist NP-vollständig, wenn es zur Komplexitätsklasse NP gehört und wenn irgendein anderes Entscheidungsproblem von NP dazu kommt. reduziert kann werden. Einige Beispiele für NP-vollständige Probleme sind die Probleme mit dem Handlungsreisenden, es Rucksackproblem und der Erfüllungsproblem. Letzteres Problem war das erste Problem, für das NP-Vollständigkeit nachgewiesen wurde.

Externer Link