Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Laufzeitangabe bei Reduktionsfunktionen
Hallo,
angenommen, eine Turingmaschine ließt in einer Eingabe etwas in der Form bin(a_1)#bin(a_2)#…#bin(a_n), mit a_1, …, a_n natürliche Zahlen. Danach rechnet man diese die Summe von diesen Zahlen aus. Was ist die Laufzeit davon? Ist das O(n) oder eher O(#Länge der Eingabe), da ja die Binärdarstellung von Zahlen je nach Größe der Zahl unterschiedlich lang ist. Darf man beim anschließenden Addieren auch davon ausgehen, dass die Addition zweier Zahlen in konstanter Zeit (d. h. O(1)) erfolgt (und wenn nicht, wie könnte man das präzisieren)?
Insbesondere in alten Braindumps musste man ja Laufzeiten, v. a. im Hinblick auf Reduktionsfunktionen, angeben. Wie muss man da vorgehen?
LG Gabriel
// Andere Sache: Ist die Definiton (vgl. Anhang) korrekt, oder wurde hier irgendwie teilweise das n mit m (bzw. umgekehrt) vertauscht (Skript Seite 39).
Attachment:
BP-Definition.png: https://fsi.cs.fau.de/unb-attachments/post_164486/BP-Definition.png
O(n) ist als Laufzeit für die Turingmaschine definitiv nicht richtig. Da Beispielsweise die Länge der Binärdarstellung der Zahlen n oder gar länger sein kann wäre es in O(n) nicht einmal möglich überhaupt die Eingabe zu lesen. D.h. hier muss man auf jeden Fall mit der Eingabelänge argumentieren. Abkürzend tut man sich leichter wenn man dafür eine Variable definiert also z.B. Sei M die Länge der Eingabe.
Insgesamt geht es zumeist nicht um das kleinstmögliche Polynom für die Laufzeit. Es ist daher am Besten/Einfachsten großzügig abzuschätzen.
Man kann möglicherweise folgendermaßen vorgehen:
Bei 3-Band Turingmaschine kann man für das Addieren 2er Zahlen in Linearer Laufzeit bezüglich der Länge der Darstellung der beiden Zahlen Zahl 1 auf Band 1, Zahl 2 auf Band 2 schreiben und anschließend auch in linearer Laufzeit (von rechts nach links) das Ergebnis auf Band 3 schreiben. Das schätzen wir großzügig mit O(M) je Addition ab. Wir können iterativ immer 2 Zahlen addieren (Das Ergebnis wird von der Darstellung nicht länger sein als die Summe der Längen der Darstellung der 2 Summanden). Insgesamt haben wir also n-1 Additionen mit jeweils O(M) Laufzeit. n-1 können wir wieder mit M abschätzen und bekommen O(M[sup]2[/sup]) Laufzeit.
Dann darf man nicht vergessen, dass es i.d.R. um 1-Band Turingmaschinen geht. Hier kann man entweder allgemein argumentieren, dass es auch eine 1-Band Turingmaschine mit polynomieller Laufzeit gibt, wenn man es mit einer 3-Band Turingmaschine in polynomieller Laufzeit schafft, oder man argumentiert konkret dass es (wenn es 3-Band Turingmaschine mit Laufzeit O(M[sup]2[/sup]) gibt) auch eine 1-Band Turingmaschine mit O((M[sup]2[/sup])[sup]2[/sup])=O(M[sup]4[/sup]) gibt, welche die Summe berechnen kann. (Im zugehörigen Satz aus der VL heißt es ja dass man k-Band-Turingmaschine mit Laufzeit t(n) und Platzbedarf s(n) in O(s(n)*t(n)) mit 1-Band Turingmaschine simulieren kann; da s(n)<=t(n) gilt auch O((t(n))[sup]2[/sup]) )
Bei der Definition von BP hat sich wohl ein Fehler eingeschlichen. Wenn ich das gerade richtig sehe, dann müsste y aus m Einträgen (nicht n) bestehen. Ansonsten sollte es passen.
1 „Gefällt mir“
Das Skript ist nun korrigiert (vgl. Changelog). Die Definition von BP sollte nun korrekt sein. Die Seitenanzahl hat sich (aufgrund des längeren Changelogs) um 1 verändert. Die Definition befindet sich nun auf Seite 40. Auf Seite 30 und auch in Blatt 8 gibt es eine äquivalente Definition von BP.
Danke für die sehr ausführliche Antwort!
Sollte man bei der Laufzeitangabe einer Reduktionsfunktion generell eine Turingmaschine verwenden oder kann man auch argumentieren, dass man diese (Reduktionsfunktion) mittels eines anderen Berechenbarkeitsmodells (z. B. RAM oder auch ein einfacher Pseudocode) berechnet, welche von einer Turingmaschine in polynomieller Zeit simuliert werden kann?
Final sollte sich die Laufzeit immer auf 1-Band-Turingmaschinen beziehen.
Pseudocode kann man prinzipiell schon nutzen - man sollte aber dann darauf achten, dass Laufzeitangaben trotzdem bezüglich Turingmaschinen gemacht werden müssen (ähnlich wie wir es in den Übungen - insbesondere in den Präsenzaufgaben - gemacht haben).
Also bei voriger Aufgabe (M:=Eingabelänge):
for i = 2 to n do // O(M) Durchläufe
a_1=a_1+a_i; // Laufzeit mit 3-Band-Turingmaschine O(M)
doneUnd dann nicht vergessen auf 1-Band-Turingmaschinenlaufzeit “umzurechnen”
Argumentationen mit Registermaschinen sind prinzipiell auch möglich. Hier ist dann aber fraglich wie (in welcher Form; muss noch irgendwas konvertiert werden? z.B. wenn Eingabe x als (1x)[sub]2[/sub] im ersten Register liegt) die Eingabe in die Registermaschine kommt. Abschließend muss aber trotzdem wieder argumentiert werden, dass das alles auch in polyomieller Laufzeit mit einer 1-Band-Turingmaschine umgesetzt werden kann.
Ist BFS strikter geworden als es früher war?
Ich wüsste nicht, ob ich in der Prüfung Lust hätte, mir die Details mit n-Band-TMs richtig auszudenken und hinzuschreiben 
Dafür ist doch die Übung da, in der wir in der Gruppe übrigens viel formalere Abgaben abgegeben hatten als gefordert waren. Insofern verstehe ich nicht, warum die Übung da bisschen handwaiving sind, die Klausur aber nicht.
Ich glaube, ich habe damals in der Klausur die polynomielle Laufzeit einfach gehandwaived und hatte trotzdem volle Punktzahl.
Das ist doch offensichtlich polynomiell
Ja, ich habe halt insbesondere deswegen nachgefragt, da in manchen Braindumps da stand: “Denken Sie daran, die Laufzeit Ihrer Reduktionsfunktion anzugeben.” (oder so ähnlich)
Zwar scheint man nach meinem Gefühl in BFS nicht unter zu großen Zeitdruck zu gelangen, aber für eine drei Punkte Aufgabe wäre das natürlich doch recht viel Aufwand.
// Edit: Was folgt dann jetzt speziell für die Klausur?
Die Ausführungen in meiner ersten Antwort waren recht ausführlich. Das alles zu schreiben muss nicht sein. Die Kernpunkte sollten aber da sein.
Ein mit Laufzeit kommentierter Pseudocode mit Nachsatz, dass polynomielle Laufzeit in Mehrband-Turingmaschine auch auf 1-Band-Turingmaschine übertragen werden kann ist IMHO weder aufwändig noch kompliziert. Dies würde ich persönlich als Mindestantwort sehen - insbesondere wenn (wie gabriel2029 schrieb) der Zusatz [quote]“Denken Sie daran, die Laufzeit Ihrer Reduktionsfunktion anzugeben.” (oder so ähnlich)[/quote] in der Aufgabe steht. Hier sich eine sinnvolle Laufzeit zu überlegen (abhängig von Eingabelänge - nicht nur abhängig von n was hier anders belegt ist) kann von jedem Studenten erwartet werden.
Auch andere Argumentationen (ohne Pseudocode) sind natürlich möglich.
Natürlich hängt es auch davon ab, wie viele Punkte in Summe für die Aufgabe vergeben werden. Bei “vielen” Punkten für diesen Teil sollte man ggf. noch genauer argumentieren. Z.B. warum JEDE der Additionen in O(M) mit 3-Band-Turingmaschine funktioniert.
Wer hier mit “Handwaving” argumentiert begibt sich in einen Graubereich. Je nach Ausprägung des Handwavings können auch Punkte abgezogen werden.
Meine Frage jetzt dazu: Wenn die Sprache, die polynomiell reduziert werden soll, kontextfrei ist, kann man dann auch einfach argumentieren, dass das Wortproblem von kontextfreien Sprachen in P ist (Satz über Korollar 3.30)? Und somit ist die Laufzeit der Reduktionsfunktion polynomiell.
Das ließe sich nämlich für das Braindump von der SS19 Klausur anwenden. Dort wurde bereits gezeigt, dass die Sprache die reguläre Pumpeigenschaft hat, und es lässt sich “relativ leicht” (etwa 15 Zustande) ein NFA bauen, der die Sprache akzeptiert. Dann ist also die Sprache regulär (Satz 3.9 + Satz 3.6) => Sprache kontextfrei => Wortproblem in P => Reduktionsfunktion in Polynomzeit berechenbar.
Müsste man dann noch beweisen, dass der NFA genau die Sprache akzeptiert die reduziert werden soll?
Prinzipiell ist das natürlich richtig und man sollte so argumentieren können.
Erstmal vorweg: die reg. Pumpeigenschaft hat hier gar keine Aussagekraft wenn du zeigen willst, dass eine Sprache kf ist.
Bei einem wirklich sehr simplen wohl nicht, in deinem Fall mit 15 Zuständen schon.
Alles in allem würde ich sagen, dass deine Idee ganz nett ist aber für die Klausur viel viel viel zu viel Aufwand für die paar Punkte.