Was ist der Unterschied zwischen "Entscheidung" und "Verifikation" in der Komplexitätstheorie?

16

In Michael Sipsers Berechnungstheorie auf Seite 270 schreibt er:

P = die Klasse von Sprachen, für die die Mitgliedschaft schnell entschieden werden kann.
NP = die Klasse von Sprachen, für die die Mitgliedschaft schnell überprüft werden kann.

Was ist der Unterschied zwischen "entschieden" und "verifiziert"?

BrotherJack
quelle
1
Übrigens, ich bin mir sicher, dass die Anführungszeichen nicht die formalen Definitionen von P und NP sind, die Sipser verwendet. Die Definitionen (oder einige der ersten Ergebnisse) sollten sich mit der Frage befassen.
Raphael

Antworten:

12

Die Aufgabe , zu entscheiden Mitgliedschaft wird: jede Eingabe gegebenen , entscheiden , ob , dh Berechne die folgende Funktion:x LxxL

χL(x)={1xL0xL

Auf der anderen Seite besteht die Aufgabe der Überprüfung der Zugehörigkeit darin, bei jeder Eingabe und einem (vorgeschlagenen) Nachweis (oder Zeugen ) der Zugehörigkeit schnell zu prüfen, ob durch diesen Nachweis ¹.xxL

Betrachten Sie zum Beispiel die Primfaktorisierung. Berechnen Sie mit alle Primfaktoren von . dagegen , überprüfen Sie, ob . Welches ist einfacher? n ( n , { i 1 , , i k } ) k j = 1 i j = nnNn(n,{i1,,ik})j=1kij=n

Ein weiteres Beispiel: Bestimmen Sie anhand eines gewichteten Graphen , ob ein Hamilton-Kreis (der alle Knoten besucht) mit einem Gewicht von höchstens . Überprüfen Sie andererseits mit , ob der Pfad alle Knoten genau einmal besucht und höchstens . Welches ist schwieriger?G=(V,E)k(G,(v1,,vn))v1vnk


  1. Sie werden also "nein" sagen, wenn aber der Beweis falsch ist. Dies ist jedoch in Ordnung, da wir in diesem Zusammenhang nicht deterministische Maschinen betrachten. Es ist nur wichtig, dass wir den richtigen Beweis erraten und ihn (schnell) überprüfen können.xL
Raphael
quelle
Wenn Sie die Zugehörigkeit zu einer Polynomzeit mit einer deterministischen Turing-Maschine M verifizieren können , ist es relativ einfach, eine nicht deterministische TM M 'zu erstellen, die über die Zugehörigkeit entscheidet : Führen Sie einfach alle möglichen Eingaben nicht deterministisch auf und komponieren Sie dann mit M.
Romuald
8

Wenn wir Effizienzprobleme ignorieren, gibt es ein weiteres Beispiel, das den Unterschied in Analogie zeigt. Wir wissen, dass das Problem des Anhaltens nicht entschieden werden kann: Wenn ein Code für eine Turing-Maschine angegeben wird, gibt es keine effektive Möglichkeit, festzustellen, ob die Maschine anhält, wenn sie ohne Eingabe ausgeführt wird.e

Aber wenn eine Maschine tut halt, ist es nicht schwer zu jemand anderes zu beweisen: nur ihnen sagen , wie viele Schritte die Maschine läuft , bevor sie stoppt. Sie können die Maschine für so viele Schritte laufen lassen und wissen, ob Sie die Wahrheit gesagt haben (Effizienz natürlich ignorierend).

Der Satz von Stopp-Turing-Maschinen ist also nicht entscheidbar, aber überprüfbar. Beachten Sie, dass für Maschinen, die nicht anhalten , kein Nachweis erbracht werden muss. Die Überprüfung ist asymmetrisch in dem Sinne, dass nur die Mitgliedschaft in der Gruppe überprüfbar ist, nicht jedoch die Mitgliedschaft außerhalb der Gruppe.

Die Situation mit P und NP ist analog. Eine Sprache ist in NP, wenn es ein Beweissystem gibt, bei dem jedes Objekt in der Sprache einen kurzen Beweis (begrenzt durch ein Polynom in der Größe des Objekts) hat, der effizient verifiziert werden kann (mit einer Anzahl von Schritten, die durch begrenzt sind) ein Polynom in der Größe der Eingabe).

Andererseits ist eine Sprache in P, wenn es eine Möglichkeit gibt, anhand einer Anzahl von Schritten, die durch ein Polynom in der Größe des Objekts begrenzt sind, festzustellen, ob ein beliebiges Objekt in der Sprache ist oder nicht. Jetzt müssen wir uns um willkürliche Eingaben kümmern, nicht nur um Objekte in der Sprache. Dieses Problem ist jedoch symmetrisch: Befindet sich eine Sprache in P, so ist dies auch ihre Ergänzung. Die Frage, ob das Komplement jeder NP-Sprache auch eine NP-Sprache ist, ist ungelöst.

(Diese Analogie könnte nahelegen, dass NP-Probleme zu P-Problemen gehören, wie re-Mengen zu berechenbaren Mengen. Das ist zwar etwas wahr, kann aber irreführend sein. Es ist eine grundlegende Tatsache, dass eine Menge, die re und co-re ist, berechenbar ist, während Es ist nicht bekannt, ob jede Menge, die NP und Co-NP ist, in P) ist.

Carl Mummert
quelle