Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in HU-3-3

Beantwortet: Verständnis

Tue, 09 Feb 2016 08:51:44 +0000

Es geht bei der Komplexität von Sprachen immer um das Wortproblem, also die Frage, ob ein Wort in der Sprache ist oder nicht. Man kann nun für kontextfreie Sprachen entweder über Grammatiken argumentieren oder über Kellerautomaten. Bei Grammatiken gibt es Algorithmen (bspw. den nicht mehr prüfungsrelevanten CYK-Parser), die für ein gegebenes Wort $w$ und eine gegebene kontextfreie Grammatik $G$ in Laufzeit $O(n^3)$ feststellen, ob $w \in L(G)$, und damit das Wortproblem lösen.

Auf der Automatenseite kann ein nichtdeterministischer Kellerautomat $K$ in Lienarzeit ausgeben, ob $w \in L(K)$. Das sagt zunächst noch nichts aus, denn Nichtdeterminismus ist in $P$ ja nicht erlaubt - aber man kann jeden nichtdeterministischen Kellerautomaten in Laufzeit $O(n^3)$ deterministisch simulieren.

Über beide Wege haben wir also einen deterministischen Pol-Zeit-Algorithmus, der das Wortproblem löst, und damit liegen (etwas salopp formuliert) "kontextfreie Sprachen in $P$".

Typ-1-Sprachen sind $PSPACE$-vollständig, wie man über eine entsprechende Reduktion zeigen kann (das müssen Sie aber nicht können, merken Sie es sich einfach).

Typ-0-Sprachen sind nicht entscheidbar. Das wiederum sollte klar sein, da innerhalb der Typ-0-Sprachen auch solche schlimmen Probleme liegen wie das Halteproblem. Da das keine Turingmaschine entscheiden kann, wie wir aus der Vorlesung wissen, ist also das Wortproblem für Typ-0-Sprachen i.A. nicht entscheidbar.

Vielleicht können Sie nach diesen Hinweisen selber überlegen, welche Laufzeit das Wortproblem für Typ-3-Sprachen im schlimmsten Fall hat? (Am besten hier die Antwort posten!)

Viele Grüße

Lukas König

Beantwortet: Warum ist SAT nicht in polynomieller Zeit lösbar?

Tue, 22 Sep 2015 09:24:15 +0000

Dazu noch ein kurzer Nachtrag (alles, was Tobias schreibt, ist aber korrekt):

Wenn wir nur von Polynomialzeit (oder einer sonstigen Zeit-/Platzklasse) sprechen, ohne "deterministisch" oder "nichtdeterministisch" anzugeben, ist immer deterministisch gemeint. Wie Tobias erklärt hat, können wir nichtdeterministische Maschinen nicht bauen, und es bringt uns daher keinen praktischen Nutzen, wenn wir einen nichtdeterministischen Polynomialzeitalgorithmus für ein Problem kennen. Nichtdeterminismus ist nur von theoretischem Interesse, um Verhältnisse zwischen Problemklassen angeben und gewisse Beweise führen zu können. Quantencomputer sind übrigens auch nicht nichtdeterministisch, und es kann nichtdeterministische Rechner in diesem Sinne in der realen Welt gar nicht geben.

Viele Grüße

Lukas König, Friederike Pfeiffer-Bohnen und Micaela Wünsche

Beantwortet: Was für ein Automat soll denn Wörter aus L in polynomialzeit überprüfen?

Tue, 22 Sep 2015 09:22:46 +0000

Man kann ausnutzen, dass alle Wörter von L kein Wort von L_quer sind (und umgekehrt). Um zu prüfen, ob ein Wort in L liegt, muss man also nur feststellen, ob es kein Wort von L_quer ist (via CYK-Algorithmus in O(n^3).

Nur weil ein Problem allgemein sehr schwer zu lösen ist, heißt das nicht, dass es auch für (speziellere) Teilprobleme gilt (siehe z.B. DNF-SAT vs allgemeines SAT)

Gruß,

Tobias (Tutor)