Komplexitätstheorie 30.07.2024

• Prüfer: Rolf Wanka (P)
• Beisitzer: Matthias Kergaßner
• Vorbereitung: Einmal das Skript bis auf Kapitel 6 durchgegangen, fast alle Beweise durchgedacht. Hat gut funktioniert.
• Die Atmosphäre war entspannt, weil Prof. Wanka zwischendrinnen immer wieder relativ lange Sachen nochmal erklärt hat. Ich hab das Gefühl es ist Prof. Wanka vor allem wichtig, dass man den Stoff versteht. Die Benotung war sehr nett. Musste mich konzentrieren „Doppelkreuz“ statt „Hashtag“ zu sagen.

P: Sie haben ja BFS gehört, von da kennen Sie ja Sprachen mit w Doppelkreuz w. Hier hatten wir ja w Doppelkreuze. Dafür ist die untere Schranke auf det. 1-Band TMs ja n^2. Wieso ist das so?

A: Wir haben für den Beweis 2 Konzepte definiert: Crossing-Sequenzen und Kolmogorov-Komplexität.

Habe dann Crossing-Sequenzen und das „Pumping-Lemma“ für Crossing-Sequenzen erklärt.

A: Dann nehmen wir wieder Bezug auf L: Wenn wir zwei verschiedene w und w' haben, können diese Wörter nicht die selbe Crossing-Sequenz im Bereich der Doppelkreuze haben. Sonst könnten wir w Doppelkreuze w' zusammenkleben was nicht in L sein kann.

A: Weiter geht es mit der Kolmogorov-Komplexität

Habe dann Kolmogorov-Komplexität und Kolmogorov-Zufälligkeit erklärt.

P: Was ist denn die Grenze der Komprimierbarkeit?

Habe zuerst nicht gecheckt, auf was er hinaus will, aber er hat scheinbar nur die Begründung dafür gemeint, warum wir immer ein K-zufälliges Wort haben müssen.

P: Wie geht es dann weiter?

A: Dann haben wir 2 Behauptungen aufgestellt: Erstens, eine simple Abschätzung von unten für unsere TM M, die L entscheidet: Die Laufzeit ist immer größer als die Summe für alle Crossing-Sequenzen im Bereich der Doppelkreuze. Zweitens ist die Behauptung, die ich vorhin schon gesagt hab.

A: Dann wollen wir ja wissen, wie lang die Crossingsequenzen im Bereich der Doppelkreuze sind. Dazu haben wir eine Turingmaschine M^~ gebaut, die uns als Codierer für die Kolmogorov-Komplexität dient.

Habe dann erklärt was M^~ macht.

A: Mit l(\hat{w}) als Crosssing-Sequenz im Bereich der Doppelkreuze für M gestartet mit \hat{w}, können wir dann folgende Gleichung aufstellen:

m ≤ K(w) ≤ |G(M^~)l(\hat{w})|

A: Daraus folgt, dass l(\hat{w}) in O(m) ist. Das können wir dann in unsere Abschätzung einsetzen und erhalten O(m^2).

P: Gut, uns ist ja nicht immer nur wichtig wie viel Zeit wir brauchen, sondern auch wie viel Platz. Bei den nicht-deterministischen Komplexitätsklassen gibt es da ja PSPACE = NPSPACE. Wie haben wir das begründet?

A: Mit dem Satz von Savitch. Der besagt, dass NTAPE(s(n)) ⊆ PTAPE(s(n)^2). Alsoo für L ∈ NTAPE(s(n)) muss es ja eine s(n)-bandbeschränkten nd-TM M geben, die L entscheidet. Dann können wir oBdA annehmen, dass es nur eine Endkonfiguration K^~ gibt.

P: Ja, diese Universalisierungen gibt es immer… (sowas hat ihn glaube ich nicht so interessiert)

A: Ja, dann haben wir TEST(K_1, K_2, l, t) definiert…

Habe dann ein bisschen was von TEST aufs Blatt geschrieben und dabei erklärt.

P: Wo wird denn der zweite rekursive Aufruf ausgeführt?

A: Auf dem selben Platz.

P: Jetzt steht da ja noch t, aber wir wollen ja den Platz von s abhängig haben

A: Wir können nur |Q| * |s| * |Γ|^s viele Schritte machen, also können wir t so abschätzen.

P: Warum ist der Platzbedarf trotzdem nicht exponentiell?

A: Weil wir t binär darstellen.

P: Wie ist denn die Laufzeit? Das ist jetzt eine Transferfrage, die nicht in der Vorlesung dran kam.

A: Exponentiell

P: Ja gut, also die Laufzeit fliegt uns um die Ohren, aber das interessiert uns ja nicht.

P: Wo haben wir das denn noch gemacht, dass wir zwei Sachen auf dem selben Bereich ausgerechnet haben?

A: Beim Beweis dafür, dass KPNF PSPACE-vollständig ist.

P: Was ist denn KPNF?

A: Da haben wir alternierende Quantoren und eine Boolsche Formel in KNF dahinter.

P: Wie haben wir jetzt bewiesen, dass KPNF PSPACE-vollständig ist?

A: Erstmal muss KPNF in PSPACE sein. Dafür haben wir einen rekursiven Algorithmus über die Anzahl der Variablen definiert. Bei einer Variable ist der check ja ziemlich easy. Bei mehr Variablen haben wir dann einmal die aktuelle Variable auf 0 und einmal auf 1 gesetzt. Dann haben wir die Ergbenisse der rekursiven Aufrufe abhängig vom Quantor verundet oder verodert.

A: Als nächstes müssen wir zeigen, dass KPNF P-Space schwer ist.

P: Das haben wir ja wie bei der Masterreduktion für die NP-Vollständigkeit von SAT gemacht, nur dass die Rechnung für Probleme in PSPACE im allgemeinen exponentiell lang sein kann und wir deshalb nicht einfach eine Formel aufstellen können. Wie haben wir das gelöst?

A: Da haben wir Allquantoren eingeführt, die den Zustandsübergang V'⊢V'' durchwechseln. Damit haben wir dann eine Rekursion ähnlich wie beim Satz von Savitch. (Weiß nicht mehr genau, was ich da gesagt hab, aber es hat gepasst)