Diskussion:Nichtdeterministische Turingmaschine
Hallo,
die neueren Ergebnisse der Quantenmechanik haben ja nun das Konzept des -Quantencomputers- hervorgebracht. Konkreter, mittlerweile existiert ja schon die Quanten-Turingmaschine in der Theoretischen Informatik, der die Mächtigkeit eines Quantencomputer abbildet. Entspricht diese Quantenturingmaschine der nichtdeterministischen Turingmaschine ?
Sur3 22:51, 28. Nov 2005 (MEZ):
Ich habe fast die gleiche frage, nämlich ob eine nichtdeterministische Turingmaschine
1. wirklich nur zufällig einen Weg wählt, denn das ließe sich doch wohl realisieren, und ich wüßte nicht wie man damit ein problem besser lösen kann?!?
oder
2. alle angegebenen Alternativen gleichzeitig durchläuft, wie bei einem Quantencomputer?
oder doch ganz anders?
Ich finde auch ein Beispiel wäre nicht schlecht, am besten eines, das ein NP-Problem in P löst!
11:54, 30. Nov 2005 (CET) FreW
Die NTM ist ist nicht mit einer Übergangsfunktion sondern mit einer Übergangsrelation definiert, diese Relation wird aber nicht näher spezifiziert. Die NTM ´rät´ eine richtige Lösung, so wurde das damals im Studium Informatik vermittelt. Die Quantenturigmaschine (QTM) hingegegen befindet sich in allen Lösungszuständen gleichzeitig, ein Ergebnis wird durch eine ´Messung´ abgegriffen. Die Komplexitätsklassen von NTM und QTM sind wohl nicht identisch, nach der neueren theoretischen Informatik.
Nicht realisierbar
Es wird behauptet, dass eine NTM nach heutigem Kenntnisstand "nicht realisierbar" sei. Das stimmt so nicht, denn jede NTM-Berechnung kann auf einer DTM simuliert werden, wenngleich bei meist dramatisch erhöhter Laufzeitkomplexität. Auch eine DTM ist natürlich nur innerhalb bestimmter Grenzen hinsichtlich der Speicherkapazität realisierbar. Aragorn2 14:06, 26. Apr 2006 (CEST)
Also zum ersten: die Quantenturingmaschine entspricht nicht der nichtdeterministischen Turingmaschine, da sie sehr wohl deterministisch rechnet, wenngleich sie sich zeitweise in einer Superposition aus Zuständen befindet und damit mehrere Berechnungspfade "gleichzeit" berechnet. Einfach ausgedrückt "wissen" bei der QTM unter bestimmten Bedingungen die Berechnungspfade voneinander, bei der NTM laufen sie wirklich parallel ohne, dass ein Berechnungspfad von einem anderen beeinflusst wird.
Zum zweiten: 1. Sie wählt die Wege nicht "zufällig", sie probiert alle Berechnungspfade gleichzeitig durch. Es gibt natürlich noch die probabilistischen Turingmaschinen, die unter einer gegebenen Wahrscheinlichkeitsverteilung einen Weg wählen. D.h. man kann mit einer bestimmten Fehlergenauigkeit sagen, ob das Ergebnis richtig ist oder nicht. 2. Die QTM durchläuft nicht immer alle Berechnugnspfade gleichzeitig. Die NTM jedoch schon. Und wenn ich ein Beispiel angeben könnte, dass ein Problem aus NP in P gelößt wird, dann hätte ich ne Menge mehr Geld ;) Mal ganz im Ernst, eine NTM probiert alle Wege parallel durch, kann aber in polynomieller Zeit verifizieren, ob eine Lösung richtig ist. Daher _N_ichtdeterministisch _P_olynomiell. Nebenbei bemerkt wurde von Bennet und Bernstein (Strength and weaknesses of quantum computing, SIAM Journal of Computer Sciences Vol. 26., No. 5, pp. 1510-1523, 1997) schon gezeigt, dass ein Problem aus NP nicht in unter gelöst werden kann. Also doch nicht polynomiell.
Zum Thema Realisierbarkeit: Wenn ich eine NTM mit einer DTM simuliere, dann ist sie ja nicht realisiert, sondern halt _simuliert_. Wenn ich natürlich nur eine ganz begrenzte Wortmenge in der Sprache habe kann ich eine NTM simulieren, indem ich parallel alle Pfade auf Korrektheit prüfe. Läßt sich nur nicht generalisieren. --Fraterq 11:29, 17. Nov. 2006 (CET)
Nein, Geld bekommen Sie erst, wenn Sie ein NP-vollstaendiges Problem in P loesen. Jedes P-Problem liegt ja trivialerweise in NP. Insbesondere muessen Bennet und Bernstein etwas anderes gesagt haben. Wahrscheinlich haben sie gezeigt, dass jedes NP-Problem deterministisch unter also schlimmstenfalls in exponentieller Zeit geloest werden kann. Das stimmt jedenfalls.
--TB 0:05, 25. Nov. 2006 (CET)
Ungenauigkeit?
Im Text steht: "Es ist eine allgemeine Fehleinschätzung, dass Quantencomputer NTMs entsprächen. NTMs können NP-vollständige Probleme lösen, Quantencomputer aber nicht."
Meiner Meinung nach kann sogar jeder stinknormale Computer NP-vollständige Probleme lösen, nur eben nicht in polynomieller Laufzeit.
- Genau das wollte ich eben auch anmerken ;) --89.247.114.105 13:14, 21. Feb. 2007 (CET)
Es sind keine weiteren Bedingungen an die Übergangsrelation genannt. Auch habe ich hier aus anderen Quellen bisher keine konkreteren Angaben gefunden. Es scheint aber implizit immer angenommen zu werden, dass es für jeden Zustand mindestens einen Nachfolgezustand gibt (also d.h. es gibt eine Teilmenge der Relation, welche eine Funktion ist). Ist das korrekt? Hierauf sollte denke ich im Text hingewiesen werden, da es ja nicht unbedeutend ist. --Albertzeyer 18:30, 23. Mär. 2007 (CET)