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

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"?

Die Aufgabe , zu entscheiden Mitgliedschaft wird: jede Eingabe gegebenen , entscheiden , ob , dh Berechne die folgende Funktion:x ∈ $x$$x \in L$

$\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$

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 ¹.$x$$x\in L$

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 = $n \in \mathbb{N}$$n$$(n, \{i_1, \dots, i_k\})$$\prod_{j=1}^k i_j = 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, (v_1, \dots, v_n))$$v_1 \to \dots \to v_n$$k$

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.$x \in L$

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.