Wie berechnen nichtdeterministische Turingmaschinen allgemeine Funktionsprobleme?

(Ich hoffe, das wurde vorher nicht gefragt, aber ich habe nichts gefunden.)

Nach meinem Verständnis gilt der Nichtdeterminismus nur für Entscheidungsprobleme, da die Existenz eines akzeptierenden Pfades erforderlich ist . In Wikipedia wird die Klasse -easy als in deterministischer Poltime lösbar definiert, mit Zugriff auf ein Orakel für ein Entscheidungsproblem in NP. Das scheint also meine Annahme zu stützen.$NP$

Meine Frage ist: Gibt es eine akzeptierte Möglichkeit, eine nicht deterministische Turing-Maschine zu definieren, um ein allgemeines Funktionsproblem zu berechnen? (Und ist es immer ein Umweg über ein Orakel für ein Entscheidungsproblem?)

Eine akzeptierte Definition lautet wie folgt: eine Funktion $f$ (dessen Ausgabe in seiner Eingabe höchstens polynomisch ist) ist in der Klasse $\mathsf{FNP}$ wenn gegeben $x,y$ man kann in polynomialer Zeit entscheiden, ob $f(x)=y$. Vergleichen Sie dies mit der Klasse$\mathsf{FP}$, die diese Funktionen enthält $f$ so dass gegeben $x$, der Wert von $f(x)$ kann in Polynomzeit berechnet werden.

Wenn Sie über Nichtdeterminismus sprechen, müssen Sie zunächst die Idee loswerden, einen Algorithmus zu haben, den Sie ausführen, um ein Ergebnis zu erhalten. Nichtdeterministische Modelle sind nur beschreibend und nicht operativ. Es gibt keine Möglichkeit, einen nichtdeterministischen Algorithmus "auszuführen". Manchmal sagen Lehrer Dinge wie "Die Maschine rät immer richtig" oder "Wir führen alle Zweige parallel aus", aber diese Intuitionsaussagen sind auf die eine oder andere Weise unzureichend.

So akzeptieren , dass ein nichtdeterministische Maschine beschreibt einige formale Objekt. Zeitraum.

Es gibt zwei Möglichkeiten, sich über nichtdeterministische Automaten ein Bild zu machen. Betrachten Sie am unteren Ende Wandler mit endlichem Zustand . Sie sind im Wesentlichen endliche Automaten mit Ausgabe; offensichtlich reduziert FA auf sie. Im nicht deterministischen Fall kann (muss aber nicht!) Jede Eingabe zu mehreren Ausgaben führen. Daher ist es sinnvoll, das "Ergebnis" einer FT zu definieren$A$ auf $w$ als die Menge aller Ausgänge $A$ kann auf produzieren $w$. Jetzt können Sie die Vereinigung gerne über mehrere Eingabewörter hinweg übernehmen oder Vorbilder berücksichtigen und so weiter.

Betrachten Sie am anderen Ende des Spektrums NTM. Die gleiche Idee funktioniert: für jede Eingabe$w$Definieren Sie als Ausgabe den Satz aller Bandinhalte, die Sie haben können, wenn das Gerät anhält (in einem akzeptierenden Zustand) $w$.

Beachten Sie, dass nichts Sie daran hindert, vom Automaten nur eine Ausgabe pro Eingabe zu verlangen, beispielsweise beim Definieren einer Komplexitätsklasse.

Ähnlich verhält es sich mit Ressourcenbeschränkungen. Die Ideen zur Definition von Entscheidungsproblemklassen sollten sich größtenteils übertragen.