In diesen Tagen habe ich über NP-Probleme, Rechenkomplexität und -theorie studiert. Ich glaube, ich habe die Konzepte von Turing Machine endlich verstanden, aber ich habe ein paar Zweifel.
Ich kann akzeptieren, dass eine nicht-deterministische Turing-Maschine mehrere Optionen hat, was man für einen gegebenen Zustand und ein gelesenes Symbol tun kann und dass es immer die beste Option auswählt, wie von Wikipedia
angegebenWie "weiß" die NTM, welche von diesen? Aktionen, die es dauern sollte? Es gibt zwei Möglichkeiten, es zu betrachten. Man soll sagen dass die Maschine die "glücklichste ist mögliche Guesser "; es wählt immer die Übergang, der schließlich zu führt ein akzeptierender Zustand, wenn es einen solchen gibt Übergang. Das andere ist vorzustellen dass die Maschine in viele "verzweigt" Kopien, von denen jede einem von folgt die möglichen Übergänge. Während a DTM hat einen einzigen "Berechnungspfad" dass es folgt, hat ein NTM ein "Berechnungsbaum". Wenn irgendein Zweig von der Baum hält mit einem "Akzeptieren" Bedingung, sagen wir, dass das NTM akzeptiert die Eingabe.
Was ich nicht verstehen kann, ist, da dies eine imaginäre Maschine ist, was wir daraus gewinnen, dass es NP-Probleme in polynomieller Zeit lösen kann? Ich meine, ich könnte auch von einer magischen Maschine theoretisieren, die NP-Probleme in O (1) löst, was kann ich daraus gewinnen, wenn sie niemals existiert?
Vielen Dank im Voraus.
Eine nicht-deterministische Turing-Maschine ist ein kniffliges Konzept. Probieren Sie einige andere Standpunkte:
Anstatt eine magische Turing-Maschine zu betreiben, die am glücklichsten ist, renne eine noch märchenhaftere Meta-Maschine, die eine unendliche Anzahl zufällig erratener unabhängiger Turing-Maschinen in parallelen Universen aufstellt. Jede mögliche Abfolge von Vermutungen wird in irgendeinem Universum gemacht. Wenn in mindestens einem der Universen die Maschine die Eingabe anhält und annimmt, reicht das: Die Probleminstanz wird von der Meta-Maschine akzeptiert, die diese parallelen Universen einrichtet. Wenn die Maschine in allen Universen zurückweist oder nicht stoppt, weist die Meta-Maschine die Instanz zurück.
Denken Sie statt jeder Art von Raten oder Verzweigen an eine Person, die versucht, eine andere Person davon zu überzeugen, dass die Instanz akzeptiert werden sollte. Die erste Person stellt die Auswahlmenge bereit, die von der nicht-deterministischen Turing-Maschine getroffen werden kann, und die zweite Person prüft, ob die Maschine die Eingabe mit diesen Auswahlmöglichkeiten akzeptiert. Wenn dies der Fall ist, ist die zweite Person überzeugt; Wenn dies nicht der Fall ist, ist die erste Person gescheitert (was entweder darauf zurückzuführen ist, dass die Instanz nicht mit einer beliebigen Folge von Auswahlmöglichkeiten akzeptiert werden kann oder weil die erste Person eine schlechte Abfolge von Auswahlmöglichkeiten gewählt hat).
Vergessen Turing Maschinen. Ein Problem ist in NP, wenn es durch eine Formel in existenzieller Logik zweiter Ordnung beschrieben werden kann. Das heißt, Sie nehmen eine plain-vanilla-aussagenlogik an, lassen Quantoren über aussagenlogischen Variablen zu und ermöglichen es, zu Beginn existenzielle Quantoren über Sätzen, Relationen und Funktionen anzuheften. Zum Beispiel kann die Graph-Dreifarbigkeit durch eine Formel beschrieben werden, die mit der existenziellen Quantifizierung über Farben (Knotengruppen) beginnt:
∃ R ∃ G ∃ B
Jeder Knoten muss farbig sein:
∃ R ∃ G ∃ B (∀ x (R (x) ∨ G (x) ∨ B (x)))
und keine zwei benachbarten Knoten dürfen die gleiche Farbe haben - nennen Sie die Kantenbeziehung E:
∃ R ∃ G ∃ B (∀ x (R (x) ∨ G (x) ∨ B (x))) ∧ (∀ x, y ¬ (E (x, y) ∧ ((R (x) R (y)) (G (x) G (y)) (B (x) B (y)))))
Die existentielle Quantifizierung über Variablen zweiter Ordnung ist wie eine nicht-deterministische Turing-Maschine, die perfekte Vermutungen macht. Wenn Sie jemanden davon überzeugen wollen, dass eine Formel ∃ X (...) wahr ist, können Sie damit beginnen, den Wert von X zu geben. Diese Polynom-Zeit-NTMs und diese Formeln sind nicht nur "ähnlich", sondern tatsächlich gleichwertig mit Fagin's Theorem das Feld der beschreibenden Komplexität gestartet: Komplexitätsklassen, die nicht durch Turing-Maschinen, sondern durch Klassen logischer Formeln gekennzeichnet sind.
Du hast auch gesagt
Ich könnte auch eine magische Maschine theoretisieren, die NP-Probleme in O (1) löst
Ja, das kannst du. Diese werden oracle machines genannt (keine Beziehung zum DBMS) und sie haben zu interessanten Ergebnissen in der Komplexitätstheorie geführt. Zum Beispiel besagt das Baker-Gill-Solovay-Theorem, dass es Orakeln A und B gibt, so dass für Turing-Maschinen, die Zugang zu A haben, P = NP, aber für Turing-Maschinen, die Zugang zu B haben, P ∈ NP. (A ist ein sehr mächtiges Orakel, das Nichtdeterminismus irrelevant macht; die Definition von B ist etwas kompliziert und beinhaltet einen Diagonalisierungstrick.) Dies ist eine Art Metaergebnis: Jeder Beweis, der die P vs NP-Frage löst, muss sensitiv sein Genug für die Definition einer Turing-Maschine, dass sie fehlschlägt, wenn Sie einige Arten von Orakeln hinzufügen.
Der Wert von nicht-deterministischen Turing-Maschinen besteht darin, dass sie eine vergleichsweise einfache, rechnerische Charakterisierung der Komplexitätsklasse NP (und anderer) bieten: Anstelle von Berechnungsbäumen oder logischen Formeln zweiter Ordnung kann man sich ein fast Alltägliches vorstellen Computer, der (vergleichsweise) leicht modifiziert wurde, so dass er perfekte Vermutungen machen kann.
Was Sie daraus ziehen, ist, dass Sie beweisen können, dass ein Problem in NP ist, indem Sie beweisen, dass es durch eine NTM in polynomieller Zeit gelöst werden kann.
Mit anderen Worten können Sie NTMs verwenden, um herauszufinden, ob ein bestimmtes Problem in NP liegt oder nicht.
Per Definition steht NP für nichtdeterministische Polynomzeit, wie in Wikipedia nachgeschlagen werden kann .
Eine Inkarnation einer nichtdeterministischen Turingmaschine, die nach dem Zufallsprinzip die nächste mögliche Lösung auswählt und untersucht (oder zusammensetzt), wird ein NP - Problem in polynomieller Zeit mit einer gewissen Wahrscheinlichkeit lösen (es würde das Problem in Polyzeit mit absoluter Sicherheit lösen, wenn es das wäre) "glücklichste mögliche Guesser").Wenn man sagt, dass ein NTM ein Problem in polynomieller Zeit lösen kann, bedeutet dies effektiv, dass dieses Problem in NP ist. Dies entspricht wiederum der Definition der NP-Klasse von Problemen.
Ich denke, deine Antwort liegt in deiner Frage. Mit anderen Worten, bei einem Problem können Sie beweisen, dass es ein NP-Problem ist, wenn Sie ein NTM finden, das es löst.
NP-Probleme sind eine spezielle Klasse von Problemen, und das NTM ist nur ein Werkzeug, um zu überprüfen, ob das gegebene Problem zu der Klasse gehört oder nicht.
Beachten Sie, dass das NTM keine bestimmte Maschine ist - es ist eine ganze Klasse von Maschinen mit genau definierten Regeln, was sie tun können und was nicht. Um "magische" Maschinen zu verwenden, müssen Sie sie definieren und zeigen, welcher Komplexitätsklasse der Probleme sie entsprechen.
Siehe Ссылка für weitere Informationen.
Aus hebräischer Wikipedia - "NTM ist hauptsächlich ein Werkzeug zum Denken, und es ist unmöglich, eine solche Maschine wirklich zu implementieren". Sie können den Begriff "NTM" durch "Algorithmus, der bei jedem Schritt alle möglichen Schritte versucht" oder "Algorithmus, der bei jedem Schritt den bestmöglichen nächsten Schritt wählt" ersetzen. Und ich denke, Sie verstehen den Rest. NTM ist hier nur um uns zu helfen, einen solchen Algorithmus zu visualisieren. Sie können hier wie es Ihnen helfen soll, sich vorzustellen (bei Pascal Cuoqs Antwort).
Was wir gewinnen ist, dass wenn wir die magische Kraft haben, den korrekten Schritt zu erraten, der sich immer als richtig herausstellen wird, können wir NPC-Probleme in POLYTIME lösen. Natürlich können wir den richtigen Schritt nicht immer "erraten". Also ist es imaginär. Aber genauso wie imaginäre Zahlen auf reale Probleme anwendbar sind, können Konsequenzen theoretisch nützlich sein.
Ein positiver Aspekt der Morphing der ursprünglichen Probleme ist, dass wir sie aus verschiedenen Blickwinkeln angehen können. In einem theoretischen Bereich ist es eine gute Sache, weil wir (1) mehr Ansätze haben können (also mehr Papiere) und (2) mehr Werkzeuge, die wir verwenden können, wenn sie in anderen Bereichen formuliert werden können.
Tags und Links complexity-theory theory turing-machines