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 Like
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.
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 Like
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
