Komplexitätsklasse des Halteproblems

von Oliver Emmler » Sonntag, 18. September 2005



Das Halteproblem ist - soweit ich das beurteilen kann -
semi-entscheidbar und damit kann nicht gesagt werden ob es
deterministisch noch nicht-deterministisch ist. Damit kann ich es auch
weder der Komplexitätsklasse P noch der Klasse NP zuordnen.

Kann ich es somit überhaupt einer Komplexitätsklasse zuordneng oder
entfällt das aufgrund der Semientscheidbarkeit?

Oliver Emmler




Re: Komplexitätsklasse des Halteproblems

von Bastian Katz » Sonntag, 18. September 2005



X-No-Archive: Yes



Ein Problem ist per se nicht deterministisch oder nichtdeterministisch.
Die Zuordnung zu P bzw. NP sagt etwas darüber aus, wie komplex es im
jeweiligen Maschinenmodell ist.


Nach den mir bekannten Definitionen müßten Turingmaschinen, die eine
Komplexität belegen sollten, auf jeder Eingabe halten. So eine Maschine
könnte aber nicht korrekt sein für das Halteproblem, also entfällt die
Komplexitätszuordnung, ja.

Gruß



Re: Komplexitätsklasse des Halteproblems

von Till Crueger » Montag, 19. September 2005







Zunächst einmal müsste man die Komplexitätsfunktion auf die Exemplare
einschränken, für die der Semi-Entscheider eine antwort ausgibt.
Allerdings wird man selbst dann keine Funktion finden um die Komplexität
auszudrücken. Der Beweis dafür sieht folgendermaßen aus:

Angenommen es gäbe eine Funktion f(n), mit der sich die Komplexität
eines echt Semi-Entscheibaren Problems ausdrücken lässt. Dann erstellen
wir eine TM die f(n) Schritte lang versucht das Problem zu lösen und
danach verwerfend anhält. Da wir aber wissen, dass alle Lösungen für
Probleme der Größe n maximal f(n) Schritte brauchen, haben wir aus einem
Semi-Entscheider einen Entscheider gebaut. D.h Das Problem ist nicht echt
Semi-Entscheidbar, also Widerspruch.

Gruß,
Till

--
Please add "Salt and Pepper" to the subject line to bypass my spam filter




Re: Komplexitätsklasse des Halteproblems

von Markus Steinborn » Sonntag, 25. September 2005



This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.

Hallo Till,





Tja, und hier ist das Problem. Warum sollte die Funktion f(n) berechenbar
sein, nur weil es eine Funktion f(n) gibt???

So kann man in der Tat zeigen, dass die Funktion f(n) nicht
turing-berechenbar ist.


Die Funktion f(n) existiert selbstverständlich: Für feste Eingabelänge
gibt es nur endlich viele Strings über einen festen endlichen Alphabet,
davon codieren nur endlich viele immer haltende
Turingmaschinen/Eingabekombinationen. Aus denen das Maximum der Laufzeit
zu bilden ist daher wohldefiniert (max. über endlich viele wohldef.
Funktionen). Es folgt direkt die Existenmz von f(n) für dieses feste, aber
beliebige n.


Grüße

Markus



If you have any questions, you can contact us: admin#mofeel.net     Spam Report