Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Fehlende Lösung (Aufgabe 5 - Nachklausur 2013)

+1 Punkt
182 Aufrufe
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.
Gefragt 12, Jan 2018 in 2013-N-05 von Anonym  
Bearbeitet 12, Jan 2018

Eine Antwort

0 Punkte

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.

Beantwortet 12, Jan 2018 von Lukas König Dozent (10,065,100 Punkte)  
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.
...