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 minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

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