NP (Komplexitätsklasse)

Der Begriff NP (von englisch Non-deterministic Polynomial time) stammt aus der Komplexitätstheorie. Er bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabe in Polynomialzeit entschieden werden können.

Äquivalent ist ein Entscheidungsproblem genau dann in NP, wenn es von einer deterministischen Turingmaschine in Polynomialzeit akzeptiert wird, die Zugriff hat auf eine wiederum polynomiell beschränkte, eingabespezifische Zusatzinformation. Die Aquivalenz ergibt sich kurzgefasst dadurch, dass einerseits der Nichtdeterminismus der ersten Turingmaschine ermöglicht, die zusätzliche Information zu erraten, und andererseits die zu einer positiven Antwort führenden Entscheidungen der nichtdeterministischen Turingmaschine als Zusatzinformation kodiert werden können.

Beispielsweise ist das Problem des Handlungsreisenden in NP. Gegeben ist eine Menge von Städten, deren paarweise Entfernungen und eine feste Länge $\lambda$ . Entschieden werden soll, ob eine Rundreise existiert, bei der jede Stadt nur einmal besucht wird und deren Gesamtlänge $\lambda$ nicht übersteigt. Die Zusatzinformation ist in diesem Fall einfach eine Rundreise mit genügend kleiner Länge. Dann müssen nur noch die einzelnen Entfernungen addiert und die Summe mit $\lambda$ verglichen werden.

Gelegentlich wird NP irrtümlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Dies ist aber falsch, da insbesondere die Menge der in Polynomialzeit deterministisch lösbaren Probleme eine (von vielen Wissenschaftlern als echt vermutete) Teilmenge von NP ist. Des Weiteren gibt es auch Probleme, die nicht in polynomialer Zeit gelöst werden können und deren Lösungen sich nicht in polynomialer Zeit verifizieren lassen. Diese liegen demnach auch nicht in NP.

Viele Probleme, die in der Komplexitätsklasse NP liegen, insbesondere die NP-vollständigen, lassen sich vermutlich nicht effizient lösen. Alle bekannten Algorithmen erfordern exponentiellen Rechenaufwand und es wird vermutet, dass es keine besseren Algorithmen gibt. Die Bestätigung oder Widerlegung dieser Vermutung wird als P/NP-Problem bezeichnet und gilt als eines der wichtigsten offenen Probleme der Informatik.

Die Klasse der Sprachen, deren Komplemente in NP liegen, heißt CoNP.

Beziehung zu anderen Komplexitätsklassen

Die folgenden Beziehungen sind bekannt:

NC ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME
Q ⊆ NP

Eigenschaften von NP

Die Klasse NP ist abgeschlossen unter

Weiterhin gilt:

$\mathbf{NP}\setminus\mathbf{Q} \,\,\,\,\not=\,\,\,\, \emptyset$

Offene Probleme

$\mathbf{NP}\setminus \mathbf{P} \,\,\,\,=\,\,\,\, \emptyset$ ? (P-NP-Problem)
$\mathbf{PSPACE}\setminus \mathbf{NP} \,\,\,\,=\,\,\,\, \emptyset$ ?
$\mathbf{EXPTIME}\setminus\mathbf{NP} \,\,\,\,=\,\,\,\, \emptyset$ ?
$\mathbf{NP}\setminus \mathbf{CoNP} \,\,\,\,=\,\,\,\, \emptyset$ ?

Weblinks

Komplexitätstheorie

Gourt Home::Gourt :: NP (Komplexitätsklasse)

Beziehung zu anderen Komplexitätsklassen

Eigenschaften von NP

Offene Probleme

Weblinks