NP (Komplexitätsklasse)

NP (Komplexitätsklasse)

NP (nichtdeterministisch polynomielle Zeit) ist in der Informatik 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, unter diesen die NP-vollständigen Probleme, lassen sich vermutlich nicht effizient lösen. Alle bekannten deterministischen Algorithmen für diese Probleme erfordern exponentiellen Rechenaufwand, und erfahrene Informatiker erwarten, 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. Das vielleicht bekannteste NP-vollständige Problem ist das Problem des Handlungsreisenden.

Gelegentlich wird NP irrtümlich als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Dies ist jedoch falsch: NP definiert lediglich eine obere Schranke für die Komplexität der enthaltenen Probleme, enthält aber auch die in Polynomialzeit lösbaren Probleme. Außerdem gibt es noch weitere Komplexitätsklassen, die weder von deterministischen noch von nicht-deterministischen Maschinen effizient lösbar wären, jedoch exponentiell viel Rechenzeit in Anspruch nehmen. Ein Beispiel wäre ein Algorithmus, der alle Zahlen von 1 bis 2n ausgibt.

Inhaltsverzeichnis

Ä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. Im deutschen Sprachraum hat diese Definition den Vorteil, dass sich der Ausdruck NP-Problem 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 Logik 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 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 NP genau dann, wenn es einen polynomiell rechenzeitbeschränkten Verifikator M für alle Wörter aus L mit LM = 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:

  • RL wird von einer deterministischen und polynomiell zeitbeschränkten Turingmaschine erkannt, und
  • x \in L genau dann, wenn es y gibt mit |y| \leq 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 (engl.) Name „witness relation“ für die Relation RL.

Äquivalenz der Definitionen

Gibt es eine NTM M, die L erkennt, so gibt es zu jedem x \in L eine akzeptierende Rechnung von M, welche sich in einen String αM(x) kodieren lässt. Die Relation RL ist dann RL = (xM(x)) für alle x \in 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 RL 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 RL überprüft, ob (x,y) \in L, also x \in 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 NP \cap CoNP nicht disjunkt. Es ist unklar, ob NP = CoNP 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:

LNLLOGCFLNCP ⊆ NP ⊆ PSPACE = NPSPACEEXPTIMENEXPTIME

Die folgenden echten Inklusionen sind bekannt:

LOGCFL ⊂ PSPACE
P ⊂ EXPTIME
Q ⊂ NP

Eigenschaften von NP

Die Klasse NP ist abgeschlossen unter

Offene Probleme

Die Antworten auf die folgenden Fragen sind bisher nicht bekannt:

Bekannte Probleme in NP

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

Weblinks

  • NP. In: Complexity Zoo. (englisch)

Quellen

Einzelnachweise

  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. 
  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. 
  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. 
  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. 
  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. 
  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. 

Wikimedia Foundation.

См. также в других словарях:

  • Komplexitätsklasse P — In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der… …   Deutsch Wikipedia

  • Komplexitätsklasse NP — 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 …   Deutsch Wikipedia

  • Komplexitätsklasse — Zusammenhang verschiedener Komplexitätsklassen Eine Komplexitätsklasse ist in der Komplexitätstheorie eine Kategorie von Problemen beziehungsweise von Algorithmen, zusammengefasst nach einem gemeinsamen Maß der Komplexität. Definiert wird eine… …   Deutsch Wikipedia

  • Co-RP (Komplexitätsklasse) — co RP (random polynominal) bzw. co RP(ε(n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede zu akzeptierende Eingabe mit Wahrscheinlichkeit 1… …   Deutsch Wikipedia

  • BQP (Komplexitätsklasse) — Die Komplexitätsklasse BQP (bounded error quantum polynomial time) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik. Zu BQP gehören alle Probleme, die auf einem Quantencomputer in Polynomialzeit mit einer …   Deutsch Wikipedia

  • P (Komplexitätsklasse) — In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, welche die Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind. Diese Problemklasse wird allgemein als die Klasse der… …   Deutsch Wikipedia

  • SL (Komplexitätsklasse) — In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können. Um logarithmischen Platzverbrauch definieren zu können, muss… …   Deutsch Wikipedia

  • Co-NP (Komplexitätsklasse) — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. In der Komplexitätstheorie bezeichnet Co NP eine Komplexitätsklasse …   Deutsch Wikipedia

  • PH (Komplexitätsklasse) — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie)… …   Deutsch Wikipedia

  • RP (Komplexitätsklasse) — RP (random polynomial) bzw. RP( (n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus A mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für… …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»