Fehlende Lösung (Aufgabe 5 - Nachklausur 2013)

Question

Für Aufgabe 5 aus der Nachklausur 2013 fehlt (wie bereits in mehren anderen Fragen erwähnt) für Telaufgabe a) und b) die Lösung.  Leider fehlt mir ein Ansatz, wie die Aufgabe zu lösen ist. Wäre es evtl. möglich eine Lösung zu veröffentlichen bzw. die Vorgehensweise kurz zu erläutern.

Ergänzung:
Ich bin mir nicht sicher, wie die Komplexitätsklasse einer Sprache genau definiert ist. Ist bei der Einordnung ausschlaggeben, dass eine Turingmaschine existiert, die bei Eingabe eines gültigen Wortes in polinomieller Zeit in einem Endzustand terminiert oder ist hierfür die Zeitkomplexität des Wortproblems ausschlaggebend. In diesem Fall müsste nach meinem Verständnis für die L-Komplement  lediglich das Ergebnis der TM, die das Wortproblem für L löst negiert werden und somit P = Co-P gelten.

Allerdings erschließt sich mir für diesen Fall nicht, warum nicht auch NP = Co-NP gelten sollte.

Answer 1

Eine Sprache (genauer: das Wortproblem einer Sprache) liegt grundsätzlich in vielen Komplexitätsklassen. Wenn ein Problem $X$ bspw. in $P$ liegt, ist es auch in $NP, PSPACE, EXPSPACE$ usw. Die Komplexität eines Problems ist die Menge an Ressourcen (etwa det. oder nichtdet. Zeit oder Platz), die es mindestens, im Mittel oder höchstens zu seiner Lösung benötigt. Umgekehrt kann man Komplexitätsklassen als Mengen von Problemen definieren, die gewissen Komplexitätseigenschaften haben. So sind in $P$ alle Probleme, die in det. Polynomialzeit gelöst werden können.

Sie haben mit Ihrer Lösung für (a) absolut recht. Im deterministischen Fall muss einfach nur die Ausgabe einer Turingmaschine für das Problem $X$ negiert werden, um eine Ausgabe für das Komplementproblem $\overline{X}$ zu erhalten. So würden wir das in der realen Welt auch mit jedem normalen Java-Programm machen, das ja stets deterministisch ist.

Im nichtdeterministischen Fall geht das aber nicht, was man sieht, wenn man sich die Definition der Akzeptanz eines Wortes durch eine nichtdeterministische Turingmaschine $T$ anschaut. $L(T)$ ist genau die Menge aller Wörter, für die ein akzeptierender Pfad im Berechnungsbaum existiert. Dreht man die Ausgabe einfach um, erhält man die Sprache $L'$, die alle Wörter enthält, für die kein akzeptierender Pfad existiert. Die Komplementsprache enthält dagegen die Wörter, für die mindestens ein nichtakzeptierender Pfad existiert. Das ist eine andere Menge, und deshalb kann man nicht so einfach argumentieren wie im deterministischen Fall.

Comments

Vielen Dank für die schnelle und ausführliche Antwort. Zu Aufgabenteil b) habe ich allerdings noch eine Verständnis Frage.
Wenn die Komplexität einer Sprache der Komplexität des zugehörigen Wortproblems entspricht, dann müsste doch "L liegt in NP" <=> "die charakteristische Funktion von L ist von einer nichtdeterministischen Turingmaschine in polynomieller Zeit berechenbar" gelten. Insbesondere ist dann die Sprache entscheidbar. Um nun zu entscheiden, ob ein Wort in L-Komplement (also E*\L) liegt müsste es doch ausreichen das Ergebnis der charakteristischen Funktion zu negieren.

---

Ja, genau so ist es.

---

Warum ist die Schlussfolgerung NP = Co-NP dennoch nicht möglich?
Ist die oben getroffene Annahme gültig, dann muss (nach meinem Verständnis) für jede Sprache L aus NP L-Komplement in NP liegen, da es ausreicht die charakteristische Funktion von L zu berechnen und das Ergebnis zu negieren. Folglich wäre jede Sprache aus NP Element von Co-NP.