P und NP (4) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 06:30 Do 09.02.2006 | | Autor: | mathiash |
| Aufgabe | Zeige: Falls [mm] P\neq [/mm] NP, so gibt es Sprachen [mm] L_i\in NP\setminus P,\: i\in\IN, [/mm] so daß
[mm] \forall i\in\IN\:\: L_i\leq_m^p L_{i+1}
[/mm]
und
[mm] \forall i\in\IN\:\: L_{i+1}\not\leq_m^p L_i [/mm] |
Hallo zusammen,
nochmal zur Erinnerung: [mm] \leq_m^p [/mm] ist die polynomiell zeitbeschraenkte m- oder Karp-Reduzierbarkeit, d.h.
[mm] A\leq_m^p [/mm] B genau dann, wenn es eine polynomiell berechenbare Funktion
[mm] f\colon\{0,1\}^{\star}\to\{0,1\}^{\star} [/mm] gibt mit [mm] A=f^{-1}(B)
[/mm]
(es sei dabei [mm] A,B\subseteq\{0,1\}^{\star} [/mm] angenommen).
Der in der Aufgabe behauptete Sachverhalt ist Standard und in vielen Lehrbüchern
zu finden - ob man sofort selber drauf kommt, ist natürlich eine ganz andere Frage.
Viele Grüße,
Mathias
|
|
|
