NP (Komplexitätsklasse) - LinkFang.de





NP (Komplexitätsklasse)


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 mitunter aufwändig sein, einen solchen Beweis zu finden. Eine alternative Beschreibung von NP ist also die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge in Polynomialzeit gelöst werden können. Hierbei wird eine Instanz mit „Ja“ beantwortet, wenn mindestens eine der möglichen Berechnungen der nichtdeterministischen Turingmaschine dies tut.

Besonders interessant sind Probleme, die vollständig für die Klasse NP sind. NP-vollständige 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 als die Klasse der nicht in Polynomialzeit lösbaren Probleme bezeichnet. Hier ist aber Vorsicht geboten: Die Klasse NP definiert lediglich eine obere Schranke für die Komplexität der enthaltenen Probleme und enthält auch alle in Polynomialzeit lösbaren Probleme. Richtig ist, dass NP-schwere Probleme vermutlich nicht in Polynomialzeit gelöst werden können. Es gibt aber NP-schwere Probleme, die selbst nicht in NP liegen, also noch schwerer als NP sind.

Ä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 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 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|))
  • xL genau dann, wenn es mindestens einen akzeptierenden Lauf von M auf x gibt.

Mit anderen Worten ist LNP 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 [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
  • xL 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 (engl.) 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 xL 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 xL 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 L[/math], also xL.

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 [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 Inklusionsrelationen bekannt. Nicht bekannt ist, ob jeweils eine echte Teilmengenbeziehung gilt:

LNLLOGCFLNCPNPPSPACE = NPSPACEEXPTIMENEXPTIME

Die folgenden echten Inklusionen sind bekannt:

LOGCFLPSPACE
PEXPTIME
QNP

Eigenschaften von NP

Die Klasse NP ist abgeschlossen unter

Offene Probleme

Die Antworten auf die folgenden Fragen sind bisher nicht bekannt:

  • NPP? (P-NP-Problem)
  • PSPACENP?
  • EXPTIMENP?
  • NPCo-NP?
  • Co-NPNP?

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 (Originaltitel: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).
  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 (Originaltitel: 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 (Originaltitel: 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 (Originaltitel: 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 (Originaltitel: 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 (Originaltitel: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/NP (Komplexitätsklasse) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.