B ist eine Sprache und Element von Sigma* und B ist Element von P)*, dann gilt:
Das Wortproblem zu L ist in O(m^l) Schritten zu lösen, wobei m die Wortlänge von w ist.
)*Wir sagen folgendes: Eine Sprache L ist in Klasse P, falls ihr Wortproblem von einer deterministischen Turing-Maschine mit polynomialer Laufzeit O(n^k) mit k größer-gleich 0 gelöst werden kann.
Wo gibt es einen Beweis dafür?
Hallo maximilianbob,
ich verstehe gerade deine Fragestellung nicht wirklich … Deswegen ein paar Fragen dazu:
1.) Was ist ein Element von Sigma^*? B als Sprache ist normalerweise eine Teilmenge von Sigma^*. Ich schätze das sollte w sein. Gleichzeitig ist dein w im Satz untendrunter bereits implizit allquantifiziert in einem „die jeweilige Wortlänge“ ist (siehe 3.)
2.) Was ist L im Satz untendrunter? Soll das B sein?
3.) Der Satz wie ich ihn verstehe bedeutet „Das Wortproblem zu B ist in O(m^l) Schritten zu lösen für ein l >= 0, wobei m die Wortlänge des jeweiligen Wortes sei.“
Dieser Satz ist eigentlich 1 : 1 die Definition der P-Eigenschaft von B. Damit ist auch kein Beweis notwendig.
Vlt. kann man dir aber auch mehr helfen, wenn du uns ein bisschen mehr Kontext zur Aufgabe gibst. Sprich: Wo hast du diese Aufgabe her? Von einem Dozierenden an der FAU/an einer anderen Universität? In welchem Kontext steht die Aufgabe? etc.
Herzlichen Dank und ich hoffe ich konnte etwas helfen.
Flo
Na ja, ich verstehe nur nicht, wieso die Anzahl der Berechnungsschritte einer deterministischen TM polynomial von der Größe des Inputswortes abhängt.
Bei einem konkreten B? Dann ist das ziemlich problemspezifisch. Wenn du eine konkrete Sprache definiert hast, und diese uns verrätst, dann können wir gemeinsam nach einer solchen Lösung/einem solchen Beweis suchen. Dieser wird aber mit ziemlicher Sicherheit ausnutzen, wie man das Problem löst. Ein einfaches Beispiel:
Wir betrachten die Sprache L = { a^n | n >= 0 } aller endlichen Wörter, welche nur den Buchstaben a haben. (Bei \Sigma = {a, b, c} bspw.) Wir wollen jetzt zeigen, dass L in P liegt. Damit geben wir jetzt eine determin. TM M an, welche die Sprache L entscheidet (das Wortproblem für L löst) und dabei, wenn ich M ein Wort der Länge n gebe, auch nur irgendwie n^i Schritte macht für irgendein i. Es ist klar, wie M aussehen sollte:
Gehe über das Eingabewort Buchstabe für Buchstabe, wenn kein a dann halte verwerfend, wenn Blank dann halte akzeptierend, sonst gehe nach rechts und konsumiere den Buchstaben.
Jetzt ist noch zu überlegen, wie lange M braucht um das Wortproblem bei einem Wort der Länge n zu entscheiden: Naja, wir gehen genau einmal über das Wort drüber, sprich wir machen immer genau n Schritte. Damit ist die Laufzeit polynomial in der Eingabegröße mit O(n) sogar. Effektiv ist damit L in P (was für den geneigten Leser bereits ersichtlich war als er die Sprache gesehen hat).
Hier in der Definition? Weil man das so definiert und damit voraussetzt. Da muss man nichts zeigen, wenn du eine Sprache L in P hast, so ist diese Eigenschaft erfüllt. Wenn ich dann für ein konkretes Problem zeigen kann, dass dieses in P liegt, so gibt es schöne Eigenschaften wie Schnelligkeit oder Äquivalente Berechnungsmodelle, oder sogar Unterklassen wie lineare Zeit etc. die relevant für verschiedene Anwendungen sind. Wenn du magst kann ich dazu auch was schreiben.
Ich hoffe das klärt die Frage, sonst einfach melden.
Hey, also vielleicht als Info, ich studiere nicht, sondern interessiere mich einfach dafür…
Meine Frage ist halt grundlegend folgende:
Wenn B eine Teilmenge von Sigma* und A eine Teilmenge von Sigma*, dann gilt
Ist B Element von P und gilt A ≤poly B, so ist auch A Element von P.
In dem Beweis schreibt der Autor folgendes:
Was meint der Autor hier mit "Wegen f Element von O(n^k) muss aber auch die Länge von f(w) in der Klasse O(n^k) sein.
Ah. Eine Funktion f : Sigma^* -> Sigma^* ist in O(n^k) hier, wenn es eine deterministische TM M gibt, welche diese Funktion in Zeit O(n^k) mit n als Eingabelänge berechnet. Sprich zu jedem w aus Sigma^* kann M den Wert f(w) in O(|w|^k) berechnen. Da M das Wort f(w) aufschreiben muss, kann das Wort nicht länger sein, als ~ |w|^k. Das ist mit dem zweiten Teil des Satzes gemeint. Dieses Ungefähr wird dabei durch die Klasse O(n^k) modelliert. Das hängt mit der konkreten Definition der O-Notation zusammen.
Wie kann denn aber ein Wort in O(n^k) liegen? Und wieso sind es gesamt dann O(n^(k*l))?
Ich starte zuerst mit der eigentlichen Definition der O-Notation:
Sei f eine Funktion von den natürlichen Zahlen ( IN ) in die reellen/natürlichen/… Zahlen (X). Dann bezeichnet O(f) die Klasse der folgenden Funktionen:
g : IN → X ist in O(f) genau dann, wenn ein C > 0 uned ein n_0 existiert, so dass g(n) <= C * f(n) gilt für alle n >= n_0.
Wir sagen umgangssprachlich, dass ein Wort die Länge O(n^k) hat, wenn seine Länge interpretiert als Funktion über n (Das geht, da f(w) irgendwie mit w und damit die Länge auch in Bezug zur Länge von w sprich n gesehen werden kann) ein Element dieser Klasse ist. Sprich die Länge ist eine Funktion von den natürlichen Zahlen in die natürlichen Zahlen und als solche dann ein Element einer solchen Klasse.
Zum zweiten Teil: Wir bekommen ein Wort w mit Länge n und wollen entscheiden, ob dieses Wort in A liegt oder nicht. Wir wissen folgendes durch die Reduktion: w ist in A genau dann wenn f(w) in B liegt. Nun betrachte den folgenden Algorithmus:
1.) Wandle das Wort w in f(w) um. // Laufzeit: O(n^k) per Annahme an die Reduktion
2.) Wende die TM von B auf f(w) an. // Laufzeit: O(m^l), wobei m die Länge der Eingabe ist.
Als Laufzeit ergibt sich damit folgendes für den zweiten Schritt: m ist die Länge von f(w), sprich wie wir oben bereits festgestellt haben in O(n^k). Aufgrund von dessen, wie die O-Notation funktioniert gehen wir oBdA von n^k aus: Damit ergibt sich eine Laufzeit von O((n^k)^l) = O(n^(kl)). Nun kann oBdA davon ausgegangen werden, dass l >= 1, weswegen n^(k * l) >= n^k, und somit die Gesamtlaufzeit auch in O(n^(kl)) liegt.
Ja, soweit ergibt das Sinn. Wieso liegt jetzt aber genau die Länge von w in O(n^k)?
Die Länge von w liegt selbstverständlich nicht in O(n^k), sondern hat die Länge n. Das Resultat der Reduktionsfunktion hat eine Länge, welche in O(n^k) liegt. Denn angenommen das wäre nicht so, so müsste die TM, welche die Reduktionsfunktion berechnet das Ausgabewort hinschreiben und braucht damit schon mindestens so viele Schritte wie das Wort lang ist. Ein klarer Widerspruch zur Aussage, dass die Berechnung von f mit einer TM in O(n^k) liegt.
Wieso wäre das ein Widerspruch?
Weil die TM sonst eine Laufzeit hätte, welche nicht in O(n^k) liegen kann (da ja die Wortlänge schon nicht in O(n^k) liegt). Die TM muss ja jede einzelne Stelle des Worts f(w) besuchen.
Ich denke, ich verstehe den Widerspruch nicht. Vielleicht verstehe ich auch das Beispiel einfach nicht.
Denn angenommen das wäre nicht so, so müsste die TM, welche die Reduktionsfunktion berechnet das Ausgabewort hinschreiben und braucht damit schon mindestens so viele Schritte wie das Wort lang ist. Ein klarer Widerspruch zur Aussage, dass die Berechnung von f mit einer TM in O(n^k) liegt.
Aber wenn sie mindestens so viele Worte braucht wie das Wort lang ist, ist damit nicht möglich, dass sie außerhalb O(n^k) liegt, vllt. verstehe ich auch einfach nicht wie ein Wort in O(n^k) liegen kann
Hey,ich habe dir was neues geschrieben 
Entschuldige die späte Antwort, aber ich hatte die letzten Tage einfach viel zu tun.
Wir zeigen die Aussage, dass f in O(n^k) Schritten berechenbar ist per Widerspruch: Dazu verstehen wir die Aussage erstmals wie folgt:
f ist in O(n^k) Schritten berechenbar
bedeutet, dass für eine Eingabe w der Länge n, die TM, welche f berechnet, O(n^k) Schritte macht. Ein Schritt kann dabei bedeuten, dass die Maschine sich nach links oder rechts bewegt. Um das Wort f(w) aufzuschreiben, braucht die Maschine mindestens (Länge von f(w))-Schritte, da sie ja Zeichen für Zeichen aufschreibt. Damit wissen wir jedoch auch, dass die Länge von f(w) in O(n^k) liegt, da andernfalls die TM, die f berechnet, ebenfalls mehr als O(n^k) Schritte bräuchte. (Erinnerung: Zeichen für Zeichen)
Mehr kann ich da nicht zu sagen, weil ich erhlich gesagt auch nicht verstehe wo genau dein Problem liegt.
Ja, ich glaube, ich habe es endlich verstanden ^^, wo ich so sehr darüber nachdenke, merke ich, dass es eigentlich ziemlich einfach ist
Auf jeden Fall noch eine Verständnisfrage: "
Warum hast du den Extra-Fall l=1 explizit aufgeschrieben bzw. was ist die Gesamtlaufzeit bei dir?
Naja im Prinzip könnte dein l ja auch 0 sein. Dann müsste man die Argumentation etwas anpassen, aber das klappt immer noch. l = 1 ist auch ein valider Fall, ich wollte an der Stelle einfach sagen, dass in eigentlich allen nennenswerten Fällen du ein l >= 1 hast. 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)).
Aber wieso addierst du das n^k zu dem n^(kl)?
Weil der Algorithmus zwei Schritte hat und man deswegen die Komplexität aufaddiert.
Wieso addierst du es aber zu dem n^(kl)?