Turing-Maschine in deterministische Turing-Maschine umschreiben
-
Hi,
ist es vom derzeitigen Forschungsstand aussgeschlossen, dass man eine Turing-Maschine in polynomieller Zeit in eine deterministische Turing-Maschine überführen kann (also Simulation schließe ich mal aus, da bleibt wohl nur alles durchprobieren, was offensichtlich nicht in polynomieller Zeit geht)?
-
Profi-Progger schrieb:
ist es vom derzeitigen Forschungsstand aussgeschlossen, dass man eine Turing-Maschine in polynomieller Zeit in eine deterministische Turing-Maschine überführen kann (also Simulation schließe ich mal aus, da bleibt wohl nur alles durchprobieren, was offensichtlich nicht in polynomieller Zeit geht)?
Ich glaube Deine Frage ist ein bißchen unpräzise gestellt. Die Turingmaschine lässt sich wohl in polynomieller Zeit deterministisch machen -- nämlich durch Simulation. Du kannst also in polynomieller Zeit aus einer gegebenen nicht-deterministischen Turingmaschine eine deterministische Turingmaschine machen.
Die interessante Frage (und darauf zielst Du denke ich eigentlich ab), ist aber, wie es mit der Laufzeit dieser neuen deterministischen Turingmaschine aussieht. Eigentlich interessiert uns ja nicht, ob wir eine deterministische Turingmaschine in polynomieller Laufzeit konstruieren können, sondern ob wir eine deterministische Turingmaschine mit polynomieller Laufzeit konstruieren können.
Das ist genau das gleiche wie die Frage nach P vs. NP. Diese ist nach aktuellem Stand der Forschung noch ungeklärt.
-
Jester schrieb:
Profi-Progger schrieb:
ist es vom derzeitigen Forschungsstand aussgeschlossen, dass man eine Turing-Maschine in polynomieller Zeit in eine deterministische Turing-Maschine überführen kann (also Simulation schließe ich mal aus, da bleibt wohl nur alles durchprobieren, was offensichtlich nicht in polynomieller Zeit geht)?
Ich glaube Deine Frage ist ein bißchen unpräzise gestellt. Die Turingmaschine lässt sich wohl in polynomieller Zeit deterministisch machen -- nämlich durch Simulation. Du kannst also in polynomieller Zeit aus einer gegebenen nicht-deterministischen Turingmaschine eine deterministische Turingmaschine machen.
Die interessante Frage (und darauf zielst Du denke ich eigentlich ab), ist aber, wie es mit der Laufzeit dieser neuen deterministischen Turingmaschine aussieht. Eigentlich interessiert uns ja nicht, ob wir eine deterministische Turingmaschine in polynomieller Laufzeit konstruieren können, sondern ob wir eine deterministische Turingmaschine mit polynomieller Laufzeit konstruieren können.
Das ist genau das gleiche wie die Frage nach P vs. NP. Diese ist nach aktuellem Stand der Forschung noch ungeklärt.
Ja, das wollte ich wissen, nur war/bin ich mir nicht ganz sicher gewesen ob man meine Frage mit "nein" beantworten könnte und trotzdem noch die Möglichkeit bestünde, dass P=NP gilt.
-
Dazu mußt Du ein bißchen genauer sagen was "umschreiben" eigentlich bedeuten soll. Vermutlich meinst Du sowas wie "erkennt dieselbe Sprache". Und dann ist das tatsächlich gegeben. Wenn Du eine nichtdeterministische Turingmaschine T findest, die L(T) in polynomieller Zeit erkennt und sich nicht deterministisch machen lässt im Sinne von eine deterministische Turingmaschine T' konstruieren, die die Sprache L(T) akzeptiert und polynomielle Laufzeit hat, dann hast Du eine Sprache gefunden, die zwar in NP liegt, aber nicht in P.
-
Profi-Progger schrieb:
...
Whatever, gibt sich denn keiner mehr Muehe, ne anstaendige Frage oder ordentlich das Problem zu formulieren. Nein, vom aktuellen Forschungsstand her ist nichts ausgeschlossen.
-
Ich denke das liegt daran, dass viele sich für eine bestimmte Fragestellung interessieren, auch ohne sich in dem Bereich gut auszukennen. Dann fehlen natürlich die präzisen Begrifflichkeiten und die Frage wird schwammig.
Daraus können sich aber oft interessante Diskussionen ergeben, in denen dann die wichtigsten Begriff aus dem Bereich auch geklärt werden. Danach ist oftmals nicht nur die ursprüngliche Frage geklärt, sondern der OP hat auch das Wissen erworben diese Frage in Zukunft präziser und verständlicher zu formulieren.