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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
200 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.
in 2013-N-05 von  
Bearbeitet

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

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.

von Dozent (10.1m Punkte)  
0 0
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.
0 0
Ja, genau so ist es.
0 0
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.
...