„NP (Komplexitätsklasse)“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[ungesichtete Version]

[gesichtete Version]

Inhalt gelöscht Inhalt hinzugefügt

Inline

Aktuelle Version vom 4. Oktober 2024, 15:51 Uhr

In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie.

Intuitiv beschrieben, enthält NP die Entscheidungsprobleme, bei denen es für „Ja“-Antworten Beweise gibt, die effizient (in Polynomialzeit) verifiziert werden können. Es kann aber aufwändig sein, einen solchen Beweis zu finden. Alternativ kann man also NP beschreiben als die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine (NTM) in Polynomialzeit bezüglich der Eingabelänge gelöst werden können. Wenn ein Rechenzweig der NTM einen Beweis findet und erfolgreich überprüft, dann akzeptiert die die Eingabe, und die Antwort ist „Ja“.

Besonders interessant sind die NP-vollständigen Probleme. Das sind die Probleme in NP, auf die jedes andere Problem in NP polynomiell reduziert werden kann und die somit die schwierigsten Probleme in NP darstellen. NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen. Alle bekannten deterministischen Algorithmen für diese Probleme erfordern im schlechtesten Fall (für die schwierigsten Probleminstanzen) exponentiellen Rechenaufwand, und es wird vermutet, dass es keine Algorithmen gibt, die alle Probleminstanzen in polynomieller Zeit lösen. Die Bestätigung oder Widerlegung dieser Vermutung ist das P-NP-Problem, eines der wichtigsten offenen Probleme der Informatik. Das vielleicht bekannteste NP-vollständige Problem ist das Problem des Handlungsreisenden in seiner Entscheidungsversion. Dieses fragt danach, ob durch gegebene Städte eine Rundreise existiert, deren Länge eine gegebene Grenze nicht überschreitet.

Gelegentlich wird NP fälschlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Die Klasse NP definiert aber lediglich eine obere Schranke für die Komplexität der enthaltenen Probleme und enthält auch alle durch eine deterministische Maschine in Polynomialzeit lösbaren Probleme. Richtig ist, dass für NP-vollständige Probleme (und einige weitere in NP) nicht bekannt ist, ob sie deterministisch in Polynomialzeit lösbar sind; man vermutet, dass dies nicht der Fall ist.

Ä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. Das hat den Vorteil, dass sich NP-Problem im Deutschen auch als Nachweis-polynomielles Problem lesen lässt, das heißt, der Nachweis einer positiven Antwort kann in polynomiell beschränkter Zeit vollzogen werden.

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 Prädikatenlogik zweiter Stufe (SO∃) gibt, der L beschreibt.

Formale Definition

Von beiden Charakterisierungen kann man eine formale Definition wie folgt angeben:

Sprachakzeptanz-Definition

Eine Sprache $L$ ist in ${\text{NP}}$ , falls es eine nichtdeterministische Turingmaschine $M$ und ein Polynom $p$ gibt, sodass gilt:

Bei Eingabe von $x$ hält $M$ nach höchstens $p(|x|)$ Schritten (jeder Lauf von $M$ auf $x$ hat also maximal Länge $p(|x|)$ ).
$x\in L$ genau dann, wenn es mindestens einen akzeptierenden Lauf von $M$ auf $x$ gibt.

Mit anderen Worten ist $L\in {\text{NP}}$ genau dann, wenn es einen polynomiell rechenzeitbeschränkten Verifikator $M$ für alle Wörter aus $L$ mit $L(M)=L$ gibt.

Suchproblem-Definition

Eine Sprache L ist in NP, falls es eine Relation $R_{L}\subseteq \{0,1\}^{*}\times \{0,1\}^{*}$ und ein Polynom p gibt, sodass gilt:

$R_{L}$ wird von einer deterministischen und polynomiell zeitbeschränkten Turingmaschine erkannt, und
x ∈ L genau dann, wenn es y gibt mit |y| ≤ p(|x|) und $(x,y)\in R_{L}$ .

Hierbei wird y auch Zertifikat von x genannt, und, im Wahrheitsfall, ein „Beweis“ (proof) oder ein „Zeuge“ (witness) für x, daher auch der (englische) Name „witness relation“ für die Relation $R_{L}$ .

Äquivalenz der Definitionen

Gibt es eine NTM M, die L erkennt, so gibt es zu jedem x ∈ L eine akzeptierende Rechnung von M, welche sich in einen String $\alpha _{M}(x)$ kodieren lässt. Die Relation $R_{L}$ ist dann $R_{L}=(x,\alpha _{M}(x))$ für alle x ∈ L und erfüllt die obigen Eigenschaften, denn die akzeptierende Rechnung ist polynomiell in der Länge von x beschränkt und kann deterministisch in polynomieller Zeit überprüft werden.

Gibt es umgekehrt eine Relation $R_{L}$ nach obiger Definition, so kann eine NTM M konstruiert werden, die ein entsprechendes y zunächst nichtdeterministisch rät, und dann mittels einer DTM für $R_{L}$ überprüft, ob $(x,y)\in R_{L}$ , also x ∈ L.

Beziehung zu anderen Komplexitätsklassen

Die Klasse der Entscheidungsprobleme, deren Komplemente in NP liegen, wird mit Co-NP bezeichnet. NP und Co-NP sind wegen $P\subseteq {\mbox{NP}}\cap {\mbox{Co-NP}}$ nicht disjunkt. Es ist unklar, ob NP = Co-NP gilt. Dies würde jedoch aus P=NP folgen, da P unter Komplementbildung abgeschlossen ist.

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 = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE = NEXPSPACE

Die folgenden echten Inklusionen sind bekannt:

LOGCFL ⊂ PSPACE

P ⊂ EXPTIME

PSPACE ⊂ EXPSPACE

Q ⊂ NP

Eigenschaften von NP

Die Klasse NP ist abgeschlossen unter

Vereinigung
Durchschnitt
Konkatenation
Kleene-Stern
epsilon-freien Homomorphismen
inversen Homomorphismen

Offene Probleme

Die Antworten auf die folgenden Fragen sind bisher nicht bekannt:

NP ⊆ P? (P-NP-Problem)
PSPACE ⊆ NP?
EXPTIME ⊆ NP?
NP ⊆ Co-NP?
Co-NP ⊆ NP?

Bekannte Probleme in NP

Karps 21 NP-vollständige Probleme
SAT ist NP-vollständig.
Das Cliquenproblem ist NP-vollständig.
Das Hamiltonkreisproblem ist NP-vollständig.^[1]
Das Rucksackproblem ist NP-vollständig.
Independent Set ist NP-vollständig.^[2]
CSAT ist NP-vollständig.^[3]
3-SAT ist NP-vollständig.^[4]
NODE-COVER ist NP-vollständig.^[5]
Problem des Handlungsreisenden ist NP-vollständig.^[6]

Alle Probleme in P sind auch in NP enthalten, da sich aus jeder deterministischen Turingmaschine trivialerweise eine äquivalente nichtdeterministische Turingmaschine konstruieren lässt. Das Problem zu entscheiden, ob zwei Graphen zueinander isomorph sind (Graphisomorphieproblem), ist ebenfalls in NP und es ist nicht bekannt, ob es NP-vollständig ist.

Siehe auch

NP-Schwere

Weblinks

NP. In: Complexity Zoo. (englisch)

Quellen

Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, ISBN 978-0-201-53082-7

Einzelnachweise

↑ John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 461 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar). überarb. = überarbeitete.
↑ John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 457 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 449 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 453 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 460 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 469 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).

[1] John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 461 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar). überarb. = überarbeitete.

[2] John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 457 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).

[3] John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 449 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).

[4] John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 453 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).

[5] John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 460 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).

[6] John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5, S. 469 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).

[1]

[2]

[3]

[4]

[5]

[6]

@@ Zeile 1: / Zeile 1: @@
+In der [[Informatik]] bezeichnet '''NP''' (für ''nichtdeterministisch polynomielle Zeit'') eine fundamentale [[Komplexitätsklasse]] aus dem Bereich der [[Komplexitätstheorie]].
-Der Begriff '''NP''' (von [[Englische Sprache|englisch]] ''Non-deterministic Polynomial time'') stammt aus der [[Komplexitätstheorie]]. Er bezeichnet eine [[Komplexitätsklasse|Klasse]] von Problemen, die von einer [[Nichtdeterminismus|nichtdeterministischen]] [[Turingmaschine]] in [[Polynomialzeit|polynomialer]] Zeit entschieden werden können.
+Intuitiv beschrieben, enthält ''NP'' die [[Entscheidbar|Entscheidungsprobleme]], bei denen es für „Ja“-Antworten Beweise gibt, die effizient (in [[Polynomialzeit]]) verifiziert werden können. Es kann aber aufwändig sein, einen solchen Beweis zu finden. Alternativ kann man also ''NP'' beschreiben als die Klasse der Entscheidungsprobleme, die von einer [[Nichtdeterministische Turingmaschine|nichtdeterministischen Turingmaschine]] (NTM) in Polynomialzeit bezüglich der Eingabelänge gelöst werden können. Wenn ein Rechenzweig der NTM einen Beweis findet und erfolgreich überprüft, dann akzeptiert die die Eingabe, und die Antwort ist „Ja“.
-Es gibt noch eine zweite äquivalente Definition von NP als die Menge aller Probleme, für die es, wenn die Antwort ja lautet, einen entsprechenden Beweis (Zertifikat) gibt, dessen Länge durch ein [[Polynom]] in der Länge des Problems beschränkt ist, und der von einer deterministischen [[Turingmaschine]] in [[Polynomialzeit|polynomialer]] Zeit verifiziert werden kann.
+Besonders interessant sind die [[NP-Vollständigkeit|''NP''-vollständigen]] Probleme. Das sind die Probleme in ''NP'', auf die jedes andere Problem in NP [[Polynomialzeitreduktion|polynomiell reduziert]] werden kann und die somit die schwierigsten Probleme in ''NP'' darstellen. ''NP''-vollständige Probleme lassen sich ''vermutlich'' nicht effizient lösen. Alle bekannten [[Determinismus (Algorithmus)|deterministischen]] [[Algorithmus|Algorithmen]] für diese Probleme erfordern im schlechtesten Fall (für die schwierigsten Probleminstanzen) exponentiellen Rechenaufwand, und es wird vermutet, dass es keine Algorithmen gibt, die alle Probleminstanzen in polynomieller Zeit lösen. Die Bestätigung oder Widerlegung dieser Vermutung ist das [[P-NP-Problem]], eines der wichtigsten offenen Probleme der Informatik. Das vielleicht bekannteste ''NP''-vollständige Problem ist das [[Problem des Handlungsreisenden]] in seiner [[Entscheidbar|Entscheidungsversion]]. Dieses fragt danach, ob durch gegebene Städte eine Rundreise existiert, deren Länge eine gegebene Grenze nicht überschreitet.
-Ein Beispiel ist das [[Problem des Handlungsreisenden]]. Gegeben ist eine Menge von Städten, deren paarweise Entfernungen und eine feste Länge L. Frage: Gibt es eine Rundreise, bei der jede Stadt nur einmal besucht wird und deren Gesamtlänge L nicht übersteigt? Offenbar lässt sich hier eine Lösung leicht verifizieren. Bei einer gegebenen Rundreise müssen nur die einzelnen Entfernungen addiert und die Summe mit L verglichen werden.
-Häufig wird NP irrtümlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Dies ist aber falsch, da die Menge der in Polynomialzeit deterministisch lösbaren Probleme eine (vermutlich echte) Teilmenge von NP ist. Außerdem gibt es auch Probleme, die nicht in polynomialer Zeit gelöst werden können, bei denen aber nicht einmal die Lösungen in polynomialer Zeit verifiziert werden können. Solche Probleme gehören demnach auch nicht zu NP.
+Gelegentlich wird ''NP'' fälschlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Die Klasse ''NP'' definiert aber lediglich eine ''obere Schranke'' für die Komplexität der enthaltenen Probleme und enthält auch alle durch eine deterministische Maschine in Polynomialzeit lösbaren Probleme. Richtig ist, dass für [[NP-Vollständigkeit|''NP''-vollständige]] Probleme (und einige weitere in ''NP'') nicht bekannt ist, ob sie deterministisch in Polynomialzeit lösbar sind; man vermutet, dass dies nicht der Fall ist.
+== Äquivalente Charakterisierungen ==
-Viele Probleme, die in der Komplexitätsklasse NP liegen, insbesondere die [[NP-vollständig]]en, lassen sich [[P/NP-Problem|vermutlich]] nicht effizient lösen, da sie exponentiellen Rechenaufwand erfordern.
+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. Das hat den Vorteil, dass sich ''NP-Problem'' im Deutschen auch als ''Nachweis-polynomielles Problem'' lesen lässt, das heißt, der Nachweis einer positiven Antwort kann in polynomiell beschränkter Zeit vollzogen werden.
+Eine weitere Charakterisierung von ''NP'' gibt es in der [[Deskriptive Komplexitätstheorie|deskriptiven Komplexitätstheorie]].
-==Beziehung zu anderen Komplexitätsklassen==
+Nach dem [[Satz von Fagin]] ist eine Sprache ''L'' genau dann in NP, wenn es einen Satz in der existenziellen [[Prädikatenlogik zweiter Stufe]] (SO∃) gibt, der ''L'' beschreibt.
-Die folgenden Beziehungen sind bekannt:
-:[[NC (Komplexitätsklasse)|NC]] ⊆ [[P (Komplexitätsklasse)|P]] ⊆ [[NP (Komplexitätsklasse)|NP]] ⊆ [[PSPACE]] ⊆ EXPTIME ⊆ [[NEXPTIME]]
+== Formale Definition ==
-''Siehe auch'': [[P/NP-Problem]]
+Von beiden Charakterisierungen kann man eine formale Definition wie folgt angeben:
+=== Sprachakzeptanz-Definition ===
+Eine Sprache <math>L</math> ist in <math>\text{NP}</math>, falls es eine [[nichtdeterministische Turingmaschine]] <math>M</math> und ein Polynom <math>p</math> gibt, sodass gilt:
+* Bei Eingabe von <math>x</math> hält <math>M</math> nach höchstens <math>p(|x|)</math> Schritten (jeder Lauf von <math>M</math> auf <math>x</math> hat also maximal Länge <math>p(|x|)</math>).
+* <math>x\in L</math> [[Logische Äquivalenz|genau dann, wenn]] es mindestens einen akzeptierenden Lauf von <math>M</math> auf <math>x</math> gibt.
+Mit anderen Worten ist <math>L\in \text{NP}</math> genau dann, wenn es einen polynomiell rechenzeitbeschränkten Verifikator <math>M</math> für alle Wörter aus <math>L</math> mit <math>L(M) = L</math> gibt.
+=== Suchproblem-Definition ===
+Eine Sprache ''L'' ist in ''NP'', falls es eine Relation <math>R_L \subseteq \{0,1\}^* \times \{0,1\}^*</math> und ein Polynom ''p'' gibt, sodass gilt:
+* <math>R_L</math> wird von einer deterministischen und polynomiell zeitbeschränkten Turingmaschine erkannt, und
+* ''x'' ∈ ''L'' genau dann, wenn es ''y'' gibt mit |''y''| ≤ ''p''(|''x''|) und <math>(x,y) \in R_L</math>.
+Hierbei wird ''y'' auch Zertifikat von ''x'' genannt, und, im Wahrheitsfall, ein „Beweis“ (''proof'') oder ein „Zeuge“ (''witness'') für ''x'', daher auch der (englische) Name „witness relation“ für die Relation <math>R_L</math>.
+=== Äquivalenz der Definitionen ===
+Gibt es eine NTM ''M'', die ''L'' erkennt, so gibt es zu jedem ''x'' ∈ ''L'' eine akzeptierende Rechnung von ''M'', welche sich in einen String <math>\alpha_M(x)</math> kodieren lässt. Die Relation <math>R_L</math> ist dann <math>R_L = (x, \alpha_M(x))</math> für alle ''x'' ∈ ''L'' und erfüllt die obigen Eigenschaften, denn die akzeptierende Rechnung ist polynomiell in der Länge von ''x'' beschränkt und kann deterministisch in polynomieller Zeit überprüft werden.
+Gibt es umgekehrt eine Relation <math>R_L</math> nach obiger Definition, so kann eine NTM ''M'' konstruiert werden, die ein entsprechendes ''y'' zunächst nichtdeterministisch rät, und dann mittels einer DTM für <math>R_L</math> überprüft, ob <math>(x,y) \in R_L</math>, also ''x'' ∈ ''L''.
+== Beziehung zu anderen Komplexitätsklassen ==
+Die Klasse der Entscheidungsprobleme, deren [[Komplement (Mengenlehre)|Komplemente]] in ''NP'' liegen, wird mit [[Co-NP]] bezeichnet. ''NP'' und ''Co-NP'' sind wegen <math>P \subseteq \mbox{NP} \cap \mbox{Co-NP}</math> nicht [[disjunkt]]. Es ist unklar, ob ''NP'' = ''Co-NP'' gilt. Dies würde jedoch aus ''P''=''NP'' folgen, da ''P'' unter Komplementbildung abgeschlossen ist.
+Meist sind für Beziehungen zwischen Komplexitätsklassen nur [[Teilmenge|Inklusionsrelationen]] bekannt. Nicht bekannt ist, ob jeweils eine echte Teilmengenbeziehung gilt:
+: ''[[L (Komplexitätsklasse)|L]]'' ⊆ ''[[NL (Komplexitätsklasse)|NL]]'' ⊆ ''[[LOGCFL]]'' ⊆ ''[[NC (Komplexitätsklasse)|NC]]'' ⊆ ''[[P (Komplexitätsklasse)|P]]'' ⊆ ''NP'' ⊆ ''[[PSPACE]]'' = ''NPSPACE'' ⊆ ''[[EXPTIME]]'' ⊆ ''[[NEXPTIME]]'' ⊆ ''[[EXPSPACE]]'' = NEXPSPACE
+Die folgenden echten Inklusionen sind bekannt:
+: ''LOGCFL'' ⊂ ''PSPACE''
+: ''P'' ⊂ ''EXPTIME''
+: ''PSPACE'' ⊂ ''EXPSPACE''
+: ''[[Q (Komplexitätsklasse)|Q]]'' ⊂ ''NP''
+== Eigenschaften von NP ==
+Die Klasse ''NP'' ist abgeschlossen unter
+* [[Menge (Mathematik)#Vereinigung (Vereinigungsmenge)|Vereinigung]]
+* [[Schnittmenge|Durchschnitt]]
+* [[Konkatenation (Formale Sprache)|Konkatenation]]
+* [[Kleene-Stern]]
+* epsilon-freien [[Homomorphismus|Homomorphismen]]
+* inversen Homomorphismen
+== Offene Probleme ==
+Die Antworten auf die folgenden Fragen sind bisher nicht bekannt:
+* ''NP'' ⊆ ''P''? ([[P-NP-Problem]])
+* ''PSPACE'' ⊆ ''NP''?
+* ''EXPTIME'' ⊆ ''NP''?
+* ''NP'' ⊆ ''Co-NP''?
+* ''Co-NP'' ⊆ ''NP''?
+== Bekannte Probleme in NP ==
+* [[Karps 21 NP-vollständige Probleme]]
+* [[Erfüllbarkeitsproblem der Aussagenlogik|SAT]] ist ''NP''-vollständig.
+* Das [[Cliquenproblem]] ist ''NP''-vollständig.
+* Das [[Hamiltonkreisproblem]] ist ''NP''-vollständig.<ref>{{BibISBN|3827370205|Seite=461}} ''überarb.'' = überarbeitete.</ref>
+* Das [[Rucksackproblem]] ist ''NP''-vollständig.
+* Independent Set ist ''NP''-vollständig.<ref>{{BibISBN|3827370205|Seite=457}}</ref>
+* CSAT ist ''NP''-vollständig.<ref>{{BibISBN|3827370205|Seite=449}}</ref>
+* [[3-SAT]] ist ''NP''-vollständig.<ref>{{BibISBN|3827370205|Seite=453}}</ref>
+* NODE-COVER ist ''NP''-vollständig.<ref>{{BibISBN|3827370205|Seite=460}}</ref>
+* [[Problem des Handlungsreisenden]] ist ''NP''-vollständig.<ref>{{BibISBN|3827370205|Seite=469}}</ref>
+Alle Probleme in '''P''' sind auch in ''NP'' enthalten, da sich aus jeder deterministischen Turingmaschine trivialerweise eine äquivalente nichtdeterministische Turingmaschine konstruieren lässt. Das Problem zu entscheiden, ob zwei Graphen zueinander isomorph sind ([[Isomorphie von Graphen|Graphisomorphieproblem]]), ist ebenfalls in ''NP'' und es ist nicht bekannt, ob es ''NP''-vollständig ist.
+== Siehe auch ==
+* [[NP-Schwere|''NP''-Schwere]]
 == Weblinks ==
-[http://www.complexityzoo.com/#np NP im Complexity Zoo (englisch)]
+* {{Complexity Zoo|NP|N#np}}
+== Quellen ==
+* Christos H. Papadimitriou: ''Computational Complexity''. [[Addison-Wesley]], ISBN 978-0-201-53082-7
+== Einzelnachweise ==
-{{Navigationsleiste Komplexitätsklassen}}
+<references />
-[[Kategorie:Komplexitätstheorie]]
+[[Kategorie:Komplexitätsklasse]]
-[[cs:Nedeterministicky polynomiální problém]]
-[[en:NP (complexity)]]
-[[es:NP]]
-[[ja:NP]]
-[[pl:Problem NP]]