Komlexitätstheorie

Vorlesung Komplexitätstheorie - HT06


Die Vorlesung Formale Sprachen und Automaten im Herbsttrimester 2006 wird von Prof. Dr. Peter Hertling gehalten. Termin und Raum der Vorlesung:

Do. 13.15 - 14.45 Uhr, Gebäuge 36, Raum 01241



Zur Vorlesung wird ein Skript erstellt. Dieses wird jeweils kurz vor oder nach der Vorlesung auf dem Dokumentenserver der Universität der Bundeswehr München bereitgestellt, und zwar hier:

Dokumente zur Vorlesung Komplexitätstheorie
Auf dem Dokumentenserver werden auch die Übungsblätter bereitgestellt.

An dem Skript auf dem Dokumentenserver und den Übungsblättern sind nach dem ersten Ins-Netz-Stellen an den folgenden Tagen die folgenden Korrekturen und Änderungen vorgenommen worden:
  • 10.10.2006: Abschnitt 1.3: Folgerung 1.8 fehlte und musste ergänzt werden.
  • 17.10.2006: Abschnitt 1.2, Definition 1.4: Da später als Komplexitätsschranken nicht nur Funktionen mit natürlichen Zahlen als Werten betrachtet, sondern auch Funktionen mit nicht negativen reellen Werten, sind die Definitionen von Komplexitätsklassen entsprechend erweitert worden. Abschnitt 1.4: Zwischen Folgerung 1.10 und Satz 1.11 war ein in diesem Kontext falsches Beispiel angegeben worden. Es wurde entfernt. Außerdem ist eine Skizze des Beweises von Satz 1.11 ergänzt worden.
  • 24.10.2006: In Abschnitt 1.5 ist eine gegenüber der Vorlesung ``Berechenbarkeit'' leicht geänderte Definition der O-Notation ergänzt worden, siehe Definition 1.17 und Bemerkung 1.18.
  • 07.11.2006: In der Definition von DTIME(t) in Definition 1.4 musste L nicht Element von Sigma^* sein, sondern Teilmenge von Sigma^*.
  • 10.11.2006: Im rekursiven Algorithmus für PATH(x,y,i) im Beweis von Lemma 2.18 musste eine if-Abfrage korrigiert werden. Im Beweis von Satz 2.16 wurde eine Formulierung geändert. Schritt 5 im Algorithmus im Beweis von Lemma 2.22 musste korrigiert werden. Schließlich war die Definition von time_min,M in Übungsaufgabe 10 auf dem Aufgabenblatt 04 falsch.
  • 07.12.2006: Im Beweis von Satz 3.34 fehlte in der Beschreibung des Teils der konstruierten Formel, die akzeptierende Konfigurationen beschreibt (oben auf Seite 61) hinter "P-Vollständigkeit" noch "des Problems CIRCUIT-VALUE". Der Rest des Satzes wurde auch etwas abgeändert, auch inhaltlich. Die Bemerkung zum Spiel Go am Ende von Kapitel 3 wurde etwas ergänzt.
  • 21.12.2006: In der Literaturliste ist das Buch von Wegener dazugekommen.
  • 17.08.2007: Auf dem Server ist eine korrigierte Version des Skripts bereit gestellt worden. Im Folgenden sind nicht alle Korrekturen aufgelistet, sondern nur die inhaltlichen Korrekturen und die Korrekturen von Tippfehlern, die zu Missverständnissen geführt haben könnten.
    Im Beweis von Satz 1.9 ist in der vorletzten Zeile einmal space_M(x) durch O(space_M(x)) ersetzt worden. Im Beweis von Satz 1.11 musste einmal 2^(i+1) durch 2^(|i|+1) ersetzt werden. Der entsprechende Satz und der vorherige Satz sind außerdem zusammengefasst worden. Im Beweis von Lemma 1.12, Teil 2, musste in der dritten Zeile s(|x|) durch t(|x|) ersetzt werden. Im Beweis von Satz 1.25 musste in der Formel in der drittletzten Zeile auf Seite 17 einmal ein Nenner |x| durch (|x|+1) ersetzt werden. Im Beweis von Lemma 2.3 sind einige Formulierungen geändert worden. In Bemerkung 3.8 muss etwa in der Mitte das Wort w nicht Element von Sigma^* sein, sondern von Sigma^* \ L_2. In der dritten Zeile des Beweises von Satz 3.10 muss L nicht Teilmenge von NLOGSPACE sein, sondern Element von NLOGSPACE. Die Definition von CIRCUIT-VALUE in Definition 3.16 wurde sauberer formuliert. Im Beweis von Satz 3.17 mussten auf Seite 49 und auf Seite 50 die Kommentare zur Ausgabe der Ein-Band-Turingmaschine und zum Ausgabeknoten korrigiert werden. In der vierten Zeile der Beweisskizze von Satz 3.21 musste es L in NP statt L in P heißen. Im Beweis von Satz 3.34 musste in der Mitte von Seite 60 ein Exponent c log p(n) durch p(n) log c ersetzt werden. Oben auf Seite 60 musste einmal Q durch Q_n ersetzt werden. Im dritten Schritt des Beweises von Lemma 4.2 ist am Ende zur Erläuterung ein Satz eingefügt worden. Im Beweis von Satz 4.6 ist eine Formulierung geändert worden. In Satz 4.10 und Satz 4.14.3 musste p(n) >= 2 statt p(n) >= 1 vorausgesetzt werden. In den Zeilen 2 und 3 des Beweises von Satz 4.10 sollte es nicht "x nicht in L", sondern "x in L" heißen. Unten auf Seite 70 musste einmal die Komplexitätsklasse P durch PP ersetzt werden. In den Vermutungen 4.23 und 4.24 wurde der Genauigkeit halber "Schaltkreise" durch "Schaltkreisfamilien" ersetzt. In der Zeile nach Satz 4.25 und am Anfang des Beweises von Satz 4.25 muss L nicht Teilmenge von BPP sein, sondern Element. Im zweiten Absatz des Beweises von Satz 4.25 ist die Bedeutung des Binärwortes a besser erklärt worden. Auf Seite 77 ist am Ende des Beweises der Hilfsaussage genauer zwischen Mengen A von Bitvektoren und einem Vektor von Bitvektoren unterschieden worden.

Übungen


Termin und Raum der Übungen:

Do. 15.00 - 15.45 Uhr, Gebäude 36, Raum 01241


Letzte Änderung: 17 August 2007