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

Kategorien

1 Pluspunkt 0 Minuspunkte
231 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.
...