Abschlusseigenschaft von P < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Ist die Klasse P unter * (Kleene-Stern) abgeschlossen? Begründen Sie ihre Antwort ausführlich! |
Hallo, ich verzweifel gerade an der obigen Aufgabe. Ich denke, dass diese Aussage stimmt, doch ich bekomme keine DTM konstruiert, die mir L* entscheidet (polynomiell). Ich habe versucht alle möglichen Zerlegungen der Eingabe abzuschätzen und dann die Zugehörigkeit zu einem bestimmten [mm] L^i [/mm] zu suchen, aber das habe ich leider keine polynomielle Laufzeit mehr. Hat jemand einen Hinweis, wie man die DTM aufbauen kann?
Oder ist man sich über die Abschlusseigenschaft noch nicht klar - Auf jeden Fall hat sie noch niemand wiederlegt, sonst wäre P ja ungleich NP.. Schließlich gilt die Abschlusseigenschaft für NP...
vielen Dank, Anja
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:17 Mo 16.06.2008 | | Autor: | Zaed |
Hallo Anja,
die Klasse P ist bezüglich dem Kleene-Stern wirklich abgeschlossen. Das kann man prinzipiell zeigen indem man den Algorithmus von Warshall zum Erzeugen der transitiven Hülle verwendet (ich erkläre gleich wieso)...
Prinzipiell steckt soetwas wie dynamische Programmierung dahinter!
Man kann sich eine Relation schaffen, welche etwas über die Zwischenstücke des Wortes aus L* aussagt. Es kommt ja darauf an, ob wir eine gültige Zerlegung unseres Ausgangswortes finden, so dass die Fragmente alle in L liegen. Unsere Relation sieht dann wie folgt aus:
[mm] (i,j) \sim (i',j') \gdw i' = i+1[/mm] und [mm] u(i:j) \in L[/mm] sowie [mm] u(i':j') \in L[/mm]
Nun bilden wir die transitive und reflexsive Hülle dieser Relation und bekommen folgende Aussage: [mm] u \in L^{\*} \gdw \exists i,k : (1,i) \sim_T (k,n) [/mm]
Du kannst dir ja mal selbst Gedanken machen, wieso das ganze in P liegt. Prinzipiel hat es etwas damit zu tun, die Relation und ihre transitive Hülle zu erzeugen, verwende dabei, dass L in P liegt.
Gruß, Zaed
|
|
|
|
