Wie berechnen nichtdeterministische Turingmaschinen allgemeine Funktionsprobleme?

7

(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?)

lukas.coenig
quelle
Ich würde mich über eine detailliertere Antwort freuen. (Sie KÖNNEN sicherlich eine operative Sicht auf Nichtdeterminismus haben!) Aber Sie verstehen meinen Standpunkt - wenn nur ein Zweig anhält (oder Null), gibt es kein Problem, aber in jedem anderen Fall gibt es mehrere Ausgänge.
lukas.coenig
"Sie können sicherlich eine operative Sicht auf Nichtdeterminismus haben!" - Sie können es versuchen, aber auf diese Weise lügen nur Missverständnisse und Wahnsinn.
Raphael

Antworten:

6

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

Yuval Filmus
quelle
Ah, das macht sehr viel Sinn! Vielen Dank!!
lukas.coenig
Haben Sie ein Zitat für diese Definition?
AdrianN
1
Nein, aber vielleicht Wikipedia.
Yuval Filmus
3

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 definierenEIN auf w als die Menge aller Ausgänge EIN 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 EingabewDefinieren 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.

Raphael
quelle
Danke, dies war (zumindest ein Teil) der Antwort, nach der ich gesucht habe (obwohl ich vermute, dass Sie das die ganze Zeit gewusst haben ...). Ich glaube immer noch, dass die "erratenen" oder "parallelen" Methoden wichtig sind, insbesondere für Anfänger, wenn sie mit Vorsicht verwendet werden. Aber Sie haben natürlich Recht, wenn Sie sagen, dass sie nicht alle Feinheiten des Nichtdeterminismus erfassen.
lukas.coenig