NP (Komplexitätsklasse)

NP (nichtdeterministisch polynomielle Zeit) ist eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge in Polynomialzeit entschieden werden können.

Viele Probleme, die in der Komplexitätsklasse NP liegen, insbesondere die NP-vollständigen, lassen sich vermutlich nicht effizient lösen. Alle bekannten deterministischen Algorithmen für diese Probleme erfordern exponentiellen Rechenaufwand, und es wird vermutet, dass es keine effizienteren Algorithmen gibt. Die Bestätigung oder Widerlegung dieser Vermutung ist das P-NP-Problem, eines der wichtigsten offenen Probleme der Informatik.

Gelegentlich wird NP irrtümlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Dies ist jedoch falsch. NP definiert ausschließlich eine obere Schranke für die Komplexität der enthaltenen Probleme.

Das vielleicht bekannteste Problem in der Klasse NP - und eines der schwierigsten NP-vollständigen - ist das Problem des Handlungsreisenden.

Äquivalente Charakterisierungen

Nach einer alternativen Definition ist ein Entscheidungsproblem genau dann in NP, wenn eine gegebene Lösung für das entsprechende Suchproblem von einer deterministischen Turingmaschine in Polynomialzeit überprüft werden kann.

Eine weitere Charakterisierung von NP gibt es in der deskriptiven Komplexitätstheorie. Nach dem Satz von Fagin ist eine Sprache L genau dann in NP, wenn es einen Satz in der existenziellen Logik zweiter Stufe (SO∃) gibt, der L beschreibt.

Beziehung zu anderen Komplexitätsklassen

Die Klasse der Entscheidungsprobleme, deren Komplemente in NP liegen, wird mit CoNP bezeichnet. NP und CoNP sind nicht disjunkt, es ist jedoch unklar, ob NP=coNP gilt.

Meist sind für Beziehungen zwischen Komplexitätsklassen nur Inklusionsrelationen bekannt. Nicht bekannt ist, ob jeweils eine echte Teilmengenbeziehung gilt:

L ⊆ NL ⊆ LOGCFL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME

Die folgenden echten Inklusionen sind bekannt:

LOGCFL ⊂ PSPACE

P ⊂ EXPTIME

Q ⊂ NP

Eigenschaften von NP

Die Klasse NP ist abgeschlossen unter

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$ ?

Bekannte Probleme in NP

SAT ist NP-vollständig.
Das Cliquenproblem ist NP-vollständig.
Das Hamiltonkreisproblem ist NP-vollständig.
Das Rucksackproblem ist NP-vollständig.

Weblinks

NP. In: Complexity Zoo. (englisch)

Quellen

Christos H. Papadimitriou: Computational Complexity. Addison Wesley, ISBN 978-0201530827