NP ist die Klasse von Sprachen mit polynomialen Zeitprüfern
Die Klasse NP, die für „nichtdeterministische polynomielle Zeit“ steht, ist ein grundlegendes Konzept in der Computational Complexity Theory, einem Teilgebiet der theoretischen Informatik. Um NP zu verstehen, muss man zunächst den Begriff der Entscheidungsprobleme begreifen, bei denen es sich um Fragen mit einer Ja-oder-Nein-Antwort handelt. Eine Sprache bezieht sich in diesem Zusammenhang auf eine Reihe von Zeichenfolgen über ein bestimmtes Alphabet, wobei jede Zeichenfolge eine Instanz eines Entscheidungsproblems codiert.
Eine Sprache (L) heißt in NP, wenn es für (L) einen polynomiellen Zeitprüfer gibt. Ein Verifizierer ist ein deterministischer Algorithmus (V), der zwei Eingaben benötigt: eine Instanz (x) und ein Zertifikat (y). Das Zertifikat (y) wird auch als „Zeuge“ oder „Beweis“ bezeichnet. Der Prüfer (V) prüft, ob das Zertifikat (y) bestätigt, dass (x) zur Sprache (L) gehört. Formal ist eine Sprache (L) in NP, wenn es einen polynomialen Zeitalgorithmus (V) und ein Polynom (p(n)) gibt, sodass für jede Zeichenfolge (x in L) eine Zeichenfolge (y) mit ( |y|. leq p(|x|)) und (V(x, y) = 1). Umgekehrt gibt es für jede Zeichenfolge (x nicht in L) keine Zeichenfolge (y), so dass (V(x, y) = 1).
Um dieses Konzept zu verdeutlichen, betrachten wir das bekannte Problem der „Booleschen Erfüllbarkeit“ (SAT). Das SAT-Problem fragt, ob es eine Zuweisung von Wahrheitswerten zu Variablen in einer gegebenen booleschen Formel gibt, so dass die Formel als wahr ausgewertet wird. Das SAT-Problem liegt in NP, weil man bei einer gegebenen booleschen Formel (phi) und einer Zuordnung (alpha) von Wahrheitswerten zu ihren Variablen in polynomieller Zeit überprüfen kann, ob (alpha) (phi) erfüllt. Hier ist die Instanz (x) die boolesche Formel (phi) und das Zertifikat (y) die Zuweisung (alpha). Der Prüfer (V) prüft, ob (alpha) (phi) wahr macht, was in polynomieller Zeit in Bezug auf die Größe von (phi) erfolgen kann.
Ein weiteres anschauliches Beispiel ist das Problem des „Hamiltonian Path“. Bei diesem Problem wird gefragt, ob es in einem bestimmten Diagramm einen Pfad gibt, der jeden Scheitelpunkt genau einmal besucht. Das Hamilton-Pfad-Problem liegt auch in NP vor, da man bei einem gegebenen Graphen (G) und einer Folge von Eckpunkten (P) in polynomieller Zeit überprüfen kann, ob (P) ein Hamilton-Pfad in (G) ist. In diesem Fall ist die Instanz (x) der Graph (G) und das Zertifikat (y) ist die Folge von Eckpunkten (P). Der Prüfer (V) prüft, ob (P) einen Hamilton-Pfad bildet, was in polynomieller Zeit in Bezug auf die Größe von (G) erfolgen kann.
Das Konzept der Verifizierbarkeit in polynomieller Zeit ist wichtig, da es eine Möglichkeit bietet, Probleme zu charakterisieren, die effizient überprüfbar sind, selbst wenn die Lösung rechnerisch nicht durchführbar sein könnte. Dies führt zu der berühmten Frage, ob (P = NP), die fragt, ob jedes Problem, dessen Lösung in polynomieller Zeit verifiziert werden kann, auch in polynomieller Zeit gelöst werden kann. Die Klasse (P) besteht aus Entscheidungsproblemen, die in polynomieller Zeit von einer deterministischen Turingmaschine gelöst werden können. Wenn (P = NP), würde dies bedeuten, dass jedes Problem mit einem Verifizierer in polynomieller Zeit auch einen Löser in polynomieller Zeit hat. Diese Frage bleibt eines der wichtigsten offenen Probleme der Informatik.
Eine der Schlüsseleigenschaften von NP ist, dass es unter polynomialen Zeitreduktionen geschlossen ist. Eine Polynomzeitreduktion von einer Sprache (L_1) auf eine Sprache (L_2) ist eine in Polynomzeit berechenbare Funktion (f), so dass (x in L_1) genau dann, wenn (f(x) in L_2). Wenn es eine Polynomzeitreduktion von (L_1) auf (L_2) gibt und (L_2) in NP liegt, dann ist (L_1) auch in NP. Diese Eigenschaft ist von entscheidender Bedeutung für die Untersuchung der NP-Vollständigkeit, die die „schwierigsten“ Probleme in NP identifiziert. Ein Problem ist NP-vollständig, wenn es in NP liegt und jedes Problem in NP in polynomieller Zeit darauf reduziert werden kann. Das SAT-Problem war das erste Problem, dessen NP-Vollständigkeit nachgewiesen wurde, und es dient als Grundlage für den Nachweis der NP-Vollständigkeit anderer Probleme.
Um das Konzept der Überprüfbarkeit in Polynomzeit weiter zu veranschaulichen, betrachten Sie das Problem der „Teilmengensumme“. Bei diesem Problem wird gefragt, ob es eine Teilmenge einer bestimmten Menge von Ganzzahlen gibt, deren Summe einen angegebenen Zielwert ergibt. Das Teilmengensummenproblem liegt in NP, weil man bei gegebener Menge von ganzen Zahlen ( S ), einem Zielwert ( t ) und einer Teilmenge ( S' ) von ( S ) in polynomieller Zeit überprüfen kann, ob die Summe der Elemente in (S') gleich (t). Hier ist die Instanz (x) das Paar ((S, t)) und das Zertifikat (y) die Teilmenge (S'). Der Prüfer (V) prüft, ob die Summe der Elemente in (S') gleich (t) ist, was in polynomialer Zeit in Bezug auf die Größe von (S) erfolgen kann.
Die Bedeutung der Verifizierbarkeit in polynomieller Zeit geht über theoretische Überlegungen hinaus. In der Praxis bedeutet dies, dass bei Problemen in NP eine vorgeschlagene Lösung (Zertifikat) effizient überprüft werden kann, wenn sie bereitgestellt wird. Dies hat erhebliche Auswirkungen auf kryptografische Protokolle, Optimierungsprobleme und verschiedene Bereiche, in denen die Überprüfung der Richtigkeit einer Lösung wichtig ist.
Zusammenfassend umfasst die Klasse NP Entscheidungsprobleme, für die eine vorgeschlagene Lösung in polynomieller Zeit durch einen deterministischen Algorithmus verifiziert werden kann. Dieses Konzept ist grundlegend für die Theorie der rechnerischen Komplexität und hat tiefgreifende Auswirkungen sowohl auf theoretische als auch auf praktische Aspekte der Informatik. Die Untersuchung von NP, polynomieller Überprüfbarkeit und verwandten Konzepten wie der NP-Vollständigkeit ist weiterhin ein lebendiges und kritisches Forschungsgebiet.
Weitere aktuelle Fragen und Antworten zu Komplexität:
- Ist die PSPACE-Klasse nicht dasselbe wie die EXPSPACE-Klasse?
- Ist die P-Komplexitätsklasse eine Teilmenge der PSPACE-Klasse?
- Können wir beweisen, dass die Klassen Np und P gleich sind, indem wir eine effiziente Polynomlösung für jedes vollständige NP-Problem auf einem deterministischen TM finden?
- Kann die NP-Klasse gleich der EXPTIME-Klasse sein?
- Gibt es Probleme in PSPACE, für die kein NP-Algorithmus bekannt ist?
- Kann ein SAT-Problem ein NP-vollständiges Problem sein?
- Kann ein Problem zur NP-Komplexitätsklasse gehören, wenn es eine nichtdeterministische Turingmaschine gibt, die es in polynomialer Zeit löst?
- Sind P und NP tatsächlich dieselbe Komplexitätsklasse?
- Ist jede kontextfreie Sprache in der P-Komplexitätsklasse?
- Gibt es einen Widerspruch zwischen der Definition von NP als einer Klasse von Entscheidungsproblemen mit Polynomzeit-Verifizierern und der Tatsache, dass Probleme in der Klasse P auch Polynomzeit-Verifikatoren haben?
Weitere Fragen und Antworten finden Sie unter Komplexität