Beweis für eine Eigenschaft einer Polynomialsprache

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.

1 Like

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))

  1. Etwas neues:
    image

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?

  1. 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 :slight_smile:

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 Like

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?