Mein Problem ist, dass ich nicht verstehe, welche Komplexitäten du aufaddierst? Grüße
Oh, sorry für die späte Antwort, habe das erst heute gelesen. Ich will die Komplexität des Algorithmus in meinem letzten Beitrag bestimmen:
Dieser Algorithmus löst ja das Wortproblem der Turingmaschine A. Das wissen wir dank Reduktion. Schritt 1 hat eine Laufzeit von O(n^k), Schritt 2 eine Laufzeit von O(n^(kl)). Das haben wir in den letzten Antworten ausfühlich besprochen. Nun musst du diese Laufzeiten addieren, da die Schritte sequentiell ausgeführt werden. Das gibt dann die gewünschte Laufzeit.
1 „Gefällt mir“
Wurde aber bereits bewiesen, dass die Reduktion in Polynomialzeit abläuft? Hast du da einen BEweis?
Wieso aber gilt, dass die Laufzeit dann trotzdem in O(n^kl) ist?
" Das war die Aussage. Die Gesamtlaufzeit ist in O(n^(kl)), genauer wahrscheinlich O(n^(kl) + n^k), aber wegen n^(k * l) >= n^k haben wir eine Laufzeit in O(n^(kl))."
Ja, das ist die Annahme: „Gilt A <=_poly B“ Das steht so im Text von dir.
1 „Gefällt mir“
Weil im Allgemeinen gilt: Wenn f und g Funktionen sind, so ist O(f + g) = O(max { f, g }). Das ist leicht mit der Definition zu zeigen. Dann ist also O(n^(kl) + n^k) = O(max { n^(kl), n^k }) = O(n^(kl)) weil eben n^(k*l) >= n^k, da l >= 1.
1 „Gefällt mir“
Hi, ich habe insgesamt 3 Anfragen zu deinen Erklärungen
Weil im Allgemeinen gilt: Wenn f und g Funktionen sind, so ist O(f + g) = O(max { f, g }). Das ist leicht mit der Definition zu zeigen. Dann ist also O(n^(kl) + n^k) = O(max { n^(kl), n^k }) = O(n^(kl)) weil eben n^(k*l) >= n^k, da l >= 1.
Kannst du das ein bisschen genauer erklären? Was ist hier O(max{f,g} und warum ist O(n^(kl) + n^k) = O(max { n^(kl), n^k }) und O(max { n^(kl), n^k }) = O(n^(kl))
- Etwas neues:
Es geht mir um den ersten Punkt (erstes Häckchen jeweils auf den Fotos) Wenn ich die Abbildung f Element von O(n^k) habe, wieso kann ich, wenn B nicht unentscheidbar ist, DARÜBER A entscheiden? Wie kann ich also die Funktion umkrempeln quasi?
- Vielleicht hört sich das etwas komisch an, aber ich habe intensiv im Internet geguckt und nichts gefunden, was ich verstehe oder was genau meinem Problem entspricht: Hast du zufällig eine Aufgabe, die vielleicht ein bisschen schwerer ist, an der ich mich auch gerne abarbeiten kann, die sich mit genau dem Thema beschäftigt. Das wäre echt cool (Ich wollte mich noch übrigens für deine Hilfe bedanken
Zu 1. ist es wahrscheinlich sinnvoll, wenn du dir das Kapitel zur O-Notation nochmal anschaust. Ich glaube nicht, dass in dem Lehrbuch welchem du folgst keine Notiz zu dieser gemacht wurde. Wenn nicht, dann kann ich gerne noch tiefer eingehen.
Zu 2.:
Angenommen B ist entscheidbar und ich möchte A entscheiden: Ich habe die Reduktionsfunktion f, welche einem x aus dem Alphabet von A ein f(x) aus dem Alphabet von B zuordnet mit der Eigenschaft, dass
x ein Element von A ist genau dann, wenn f(x) ein Element von B ist.
Ich bekomme also ein x und möchte entscheiden, ob x in A liegt. Dazu berechne ich einfach f(x) und wende dann den Entscheider von B an. Gibt dieser mit JA zurück, so liegt x in A, sonst nicht. Damit ist auch A entscheidbar.
Zu 3.: Hier https://www.eti.uni-siegen.de/ti/lehre/ss20/gti/gti_blatt14_loesungen_final.pdf beispielsweise, oder https://www21.in.tum.de/teaching/theo/SS19/ex/lo10.pdf oder http://www-tcs.cs.uni-sb.de/media/lectures/W1516/L-GZTheoretischeInformatik/sheet8-sol_Ol1qzK3.pdf
Mehr kann ich auf die Schnelle auch nicht geben.
1 „Gefällt mir“
Hi, ja, gerne geh tiefer auf 1. ein! Das wäre sehr lieb!
Zu 2.: Jup, ist logisch
Zu 3.: Danke! Lass dir ruhig Zeit und vllt. stößt du irgendwann auf ne Aufgabe, die auch für mich passt?