Komplementsprachen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Was genau ist die Komplementsprache co-NP? |
Laut Definition ist co-NP := { [mm] \summe [/mm] ^* \ L | L [mm] \in [/mm] NP}. Mein Kollege und ich, wir haben unterschiedliche Meinungen über das, was das jetzt bedeutet.
Mein Kollege ist der Meinung, dass in co-NP alle Probleme liegen, für die die Turingmaschine in einem nicht akzeptierenden Zustand angehalten hat.
Meine Auffassung ist, dass co-NP genau die Elemente enthält, für die die Turingmaschine nicht angehalten hat. Man weiß nicht, ob sie noch anhält. Sofern sie irgendwann für alle Probleme anhält, wäre co-NP = NP, tut sie das nicht, dann wäre co-NP != NP.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mi 06.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
