Beweis, P und NP < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:55 Fr 19.01.2007 | | Autor: | g_hub |
| Aufgabe | | Beweisen Sie, dass wenn [mm] L\in [/mm] NP, dann ist [mm] L*\in [/mm] NP. Würde Ihr Beweis auch funktionieren, wenn man NP durch P ersetzt? |
Also, bei Aufgabe ist mir nicht ganz klar, was eigentlich gefragt ist. Als Antwort würde ich folgenden Algorithmus angeben:
1) Prüfe ob Eingabe w leer, wenn ja gib "0" (dh [mm] w\not\in [/mm] L*) aus
2) Sonst, simuliere (N)DTM für L auf Eingabe w.
-> funktioniert sowohl für NP als auch für P...
... irgendwo muss ich einen Denkfehler machen; kann mir jmd helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:44 Sa 20.01.2007 | | Autor: | Frank05 |
> Also, bei Aufgabe ist mir nicht ganz klar, was eigentlich
> gefragt ist. Als Antwort würde ich folgenden Algorithmus
> angeben:
>
> 1) Prüfe ob Eingabe w leer, wenn ja gib "0" (dh [mm]w\not\in[/mm]
> L*) aus
Vorsicht. In [mm]L^*[/mm] ist [mm]\varepsilon[/mm] ebenfalls enthalten. Die korrekte Ausgabe muss somit 1 sein.
> 2) Sonst, simuliere (N)DTM für L auf Eingabe w.
Nein. Das reicht nur um [mm]L[/mm] zu erkennen, aber nicht für [mm]L^*[/mm]. In letzterem sind Wörter erlaubt, die aus beliebigem Aneinanderhängen von Wörtern aus [mm]L[/mm] entstehen. Diese erkennt die TM für [mm]L[/mm] erstmal nicht (zB könnte [mm]abc, def \in L[/mm] gelten, aber [mm]abcdef \not \in L, abcdef \in L^*[/mm]).
> -> funktioniert sowohl für NP als auch für P...
... nicht.
> ... irgendwo muss ich einen Denkfehler machen; kann mir
> jmd helfen?
Du bist einfach nur an der Aufgabe vorbeigeschrammt. Mach dir nochmal genau klar, was der Unterschied zwischen [mm]L[/mm] und [mm]L^*[/mm] ist. Dann kannst du dir nochmal überlegen, was du mit der TM für [mm]L[/mm] anfangen kannst wenn du [mm]L^*[/mm] erkennen willst.
hth,
Frank
|
|
|
|
