NP-Probleme

NP-Probleme

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, genauer gesagt die NP-vollständigen Probleme, 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.

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.

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 polynom-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 nicht-deterministische Turingmaschine M und ein Polynom p gibt, sodass:

  • Bei Eingabe von x hält M nach höchstens p( | x | ) Schritten (daher jeder Lauf von M auf x hat maximal Länge p( | x | ))
  • x \in L genau dann wenn es mindestens einen akzeptierenden Lauf von M auf x 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:

  • RL wird von einer (deterministischen) 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 ein "Beweis" (proof) oder ein "Zeuge" (witness) für x genannt, 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 polynomiell ü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 CoNP bezeichnet. NP und CoNP sind nicht disjunkt, es ist jedoch unklar, ob NP=coNP gilt. (Es würde jedoch aus P=NP folgen, da P=coP.)

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

  • \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

Siehe auch

Weblinks


Quellen

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

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • problème — [ prɔblɛm ] n. m. • 1382; lat. problema, du gr. problêma 1 ♦ Question à résoudre qui prête à discussion, dans une science. Problèmes philosophiques, moraux, métaphysiques. Le problème du mal. Soulever un problème. C est là la clé, le nœud du… …   Encyclopédie Universelle

  • Probleme du sac a dos — Problème du sac à dos Le problème du sac à dos : quelles boîtes choisir afin de maximiser la somme emportée tout en ne dépassant pas les 15 kg autorisés ? Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un …   Wikipédia en Français

  • Probleme d'echecs — Problème d échecs Moyen Âge shakkinappula, kuningas. Un problème d’échecs est une énigme à valeur artistique utilisant les pièces et les règles du jeu d échecs. Un problème est créé par un compositeur dans le but de présenter un thème ou une idée …   Wikipédia en Français

  • Probleme de Monty Hall — Problème de Monty Hall Le problème de Monty Hall est un casse tête probabiliste librement inspiré du jeu télévisé américain Let s Make a Deal [1]. Il est simple dans son énoncé mais non intuitif dans sa résolution et c est pourquoi on parle… …   Wikipédia en Français

  • Probleme de la couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Probleme de la mesure quantique — Problème de la mesure quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique H …   Wikipédia en Français

  • Probleme heterodoxe — Problème d échecs Moyen Âge shakkinappula, kuningas. Un problème d’échecs est une énigme à valeur artistique utilisant les pièces et les règles du jeu d échecs. Un problème est créé par un compositeur dans le but de présenter un thème ou une idée …   Wikipédia en Français

  • Probleme orthodoxe — Problème d échecs Moyen Âge shakkinappula, kuningas. Un problème d’échecs est une énigme à valeur artistique utilisant les pièces et les règles du jeu d échecs. Un problème est créé par un compositeur dans le but de présenter un thème ou une idée …   Wikipédia en Français

  • Problème de la mesure — quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique H …   Wikipédia en Français

  • Problème de monty hall — Le problème de Monty Hall est un casse tête probabiliste librement inspiré du jeu télévisé américain Let s Make a Deal [1]. Il est simple dans son énoncé mais non intuitif dans sa résolution et c est pourquoi on parle parfois à son sujet de… …   Wikipédia en Français

  • Problème d’échecs — Problème d échecs Moyen Âge shakkinappula, kuningas. Un problème d’échecs est une énigme à valeur artistique utilisant les pièces et les règles du jeu d échecs. Un problème est créé par un compositeur dans le but de présenter un thème ou une idée …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”