P und NP (2) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 05:30 Fr 03.02.2006 | | Autor: | mathiash |
| Aufgabe | Gib zwei Sprachen [mm] L_1 [/mm] und [mm] L_2 [/mm] an , die in NP liegen, aber nicht NP-vollständig sind (unabhängig davon, ob P=NP oder [mm] P\neq [/mm] NP).
''Vollständig'' soll hier heißen: vollständig bezüglich [mm] \leq_m^p, [/mm] des funktionalen Reduktionsbegriffes, d.h. nicht Orakel-Reduzierbarkeit. |
Bezüglich Orakel-Reduzierbarkeit kann man das nicht ohne die Annahme [mm] P\neq [/mm] NP machen.
Viel Spaß und viele Grúße,
Mathias
|
|
|
