nichtdeterministische Turingmaschine
-
Zur folgenden Aufgabe hab ich eben eine falsche Lösung abgegeben (ist mir grad aufgefallen):
Wir betrachten die natürlichen Zahlen n in Dezimaldarstellung dez(n) ohne führende Nullen. Eine Zahl n>= 2 heisst zusammengesetzt, wenn sie nicht prim ist. Sei Z:={dez(n)| n>=2, n zusammengesetzt}.
Zeige Z Element von NP durch eine informelle Beschreibung einer nichtdeterministischen polynomzeitbeschränkten TM, die Z entscheidet.
Hat jemand eine Idee wie so eine NTM aussieht? Mir fällt da irgendwie nicht Sinnvolles ein.
-
Wir raten nichtdeterministisch einen Teiler p von n, und prüfen dann deterministisch, ob p wirklich Teiler von n ist. Letzteres kann man z.B. mit ganz normaler schriftlicher Division machen. Oder man addiert solange p auf, bis man n erreicht. Beides sollte in polynomieller Zeit möglich sein.
-
Draufaddieren ist glaub ich nicht in polynomieller Zeit machbar, das war nämlich mein Fehler. Bin aber jetzt auch selbst auf ne lösung gekommen, ich nehm einfach alle möglichen kombinationen aus 2 zahlen und multiplizier die miteinander, wenn bei den ergebnissen n dabei ist, dann ist n zusammengesetzt.
-
Abbadon schrieb:
Draufaddieren ist glaub ich nicht in polynomieller Zeit machbar, das war nämlich mein Fehler.
Hmm. Mal sehen. n hat log(n) Stellen, also haben sowohl m als auch auch alle Zwischensummen maximal soviele. Einmal aufaddieren sollte somit in O(log(n)) gehen, bis n aufsummieren also in O(n log(n)). Wo ist da mein Denkfehler?
Bin aber jetzt auch selbst auf ne lösung gekommen, ich nehm einfach alle möglichen kombinationen aus 2 zahlen und multiplizier die miteinander, wenn bei den ergebnissen n dabei ist, dann ist n zusammengesetzt.
Gut, das geht natürlich auch
-
Der denkfehler ist, dass sich das polynomial nicht auf das n bezieht, sondern auf die länge von n als dezimalzahl.
-
stimmt.