Nicht deterministische Turing-Maschine, die an mindestens einem Rechenzweig anhält

Ich schaue mir hier mein Lehrbuch von Michael Sipser an und er sagt, dass eine nicht deterministische Turing-Maschine ein Entscheider ist, wenn alle ihre Berechnungszweige bei allen Eingaben anhalten. Ich denke, ich erinnere mich, dass ich irgendwo etwas gesehen habe, was man als nicht deterministische Turing-Maschine bezeichnen würde, die auf mindestens einem Zweig für alle Eingaben anhält, auf anderen aber möglicherweise eine Schleife ausführt. Gibt es einen Namen für so etwas? Ich sehe später in diesem Kapitel das Wort Verifizierer , aber das scheint nicht zu passen ... Ich denke, das bezieht sich auf einen Algorithmus.

Ein Prüfer für eine Sprache ist ein Algorithmus , wobei A = \ {w \ mid V \ text {akzeptiert} \ langle w, c \ rangle \ text {für eine Zeichenfolge c} \}. Wir messen die Zeit eines Verifizierers nur anhand der Länge von w , daher läuft ein Polynomzeitverifizierer in Polynomzeit in der Länge von w . Eine Sprache A ist polynomiell überprüfbar, wenn sie einen polynomiellen Zeitprüfer hat.$A$$V$

$$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$ $w$$w$$A$

Die Idee ist, dass ein deterministisches TM immer in endlicher Zeit mit Ja / Nein antwortet (sonst macht die ganze Idee keinen Sinn). Und um dies zu erreichen, kann die deterministische Simulation des NTM nicht einfach auf einigen Zweigen ins Lala-Land gehen, dh jeder Zweig muss in einer endlichen Tiefe mit Ja / Nein enden. Es entscheidet (gibt Ihnen eine eindeutige Antwort). Wenn nicht alle Zweige anhalten, kann dies überprüft werden (dh bei einem Wort in der Sprache wird garantiert mit Ja geantwortet; wenn nicht, wird möglicherweise Nein beantwortet, möglicherweise wird eine Schleife ausgeführt).

Die Saiten von einer NTM akzeptiert Mist die Sprache M, stellte fest ,L(M)

Nehmen wir an, dass Mfür jede Eingabe nicht garantiert wird, dass sie in allen Zweigen angehalten wird. Dann Mkann eindeutig kein Entscheider sein und ist somit nur ein Erkenner. Merkennt die Sprache aller Zeichenfolgen, für die jeder Zweig von Min einem akzeptierenden Zustand endet.

Da Mes sich um einen Erkenner handelt, wird garantiert, dass eine Zeichenfolge nur akzeptiert wird, wenn die Zeichenfolge aktiviert ist L(M). Bei einer Zeichenfolge, die nicht vorhanden ist L(M), wird die Zeichenfolge möglicherweise abgelehnt oder für immer wiederholt. Jeder NTM kann von einem DTM simuliert werden. Wenn NTM jedoch nur eine Sprache erkennt L, erkennt auch der entsprechende DTM nur eine Sprache L.

Wenn der NTM in allen Zweigen für eine Eingabe anhält, ist er ein Entscheider, dann tut der entsprechende DTM dasselbe und ist somit auch ein Entscheider.

Ein Prüfer ist nicht das, wonach Sie suchen. In Sipsers Buch Einführung in die Theorie der Berechnung wird der Verifizierer vorgestellt, wenn über die Komplexität von Algorithmen und Komplexitätsklassen gesprochen wird, da jede Sprache Lgenau dann in NP ist, wenn sie einen Polynomzeitverifizierer hat.

Ein Verifizierer für eine Sprache Lwird als Eingabe einer Zeichenfolge win Lund ein Zertifikat c(man denke an das Zertifikat als Lösung des Problems w) und verifizieren , dass das Zertifikat in der Tat eine korrekte Lösung, wodurch win liegen L.

Beispiel:

Für die Sprache

L = { w | w is an integer for which the product of some of the digits equals 12000 }

Sie können einen Prüfer machen V, die einen String win Leinem Zertifikat c, und prüft , ob die win in der Tat Lmit dem Zertifikat c. ckönnte eine binäre Zeichenfolge sein, die die ganzen Zahlen angibt, wfür die das Produkt von 12000 entspricht.

VMuss zum Beispiel die Eingabe ablehnen 1923423343, 0010111011, weil2*4*2*3*4*3 = 576 != 12000

Für viele Probleme kennen wir nur einen Algorithmus, der sie lösen kann, wenn sie in exponentieller Zeit der Eingabegröße ausgeführt werden. Aus diesem Grund sind Verifizierer interessant, da es häufig der Fall ist, dass wir mit einer Lösung schnell feststellen können, ob diese Lösung richtig oder falsch ist.