Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in 2013-N-05

Fehlende Lösung (Aufgabe 5 - Nachklausur 2013)

Fri, 12 Jan 2018 12:19:12 +0000

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.

Lösungen nicht vorhanden

Fri, 05 Feb 2016 13:49:39 +0000

Ich wollte fragen, wieso bei der Nachklausur die Antworten zu einigen Fragen fehlen.

Liegt es daran, dass es nicht mehr klausurrelevant ist ?

Lösungsansätze füt a) & b)

Wed, 23 Sep 2015 14:23:46 +0000

a) Reicht es hier schon, wenn man den polynomialzeitalgorithmus von L noch einmal negiert um einen Algorthmus für L-Komplement zu bekommen? Daraus könnte man schließen, das auch dieses Problem von einem deterministischen Automaten in polynomieller Zeit gelöst werden kann und somit L-Komplement in P liegt.

b) Mein Ansatz ist hier, dass NP-Probleme von nichtdeterministischen Turingmaschinen in polynomieller Zeit gelöst werden können und somit das Problem zu lösen deutlich schwieriger ist und exponenziell so groß ist wie Probleme, die von einer deterministischen Turingmaschine gelöst werden können.

Was fehlt hier noch in der Argumentation?-