- Mi, 13.04.05 (Nicole Schweikardt):
Organisatorisches sowie Kapitel 0: Einleitung und Kapitel 1.1: Logik erster Stufe (FO)
(Seiten 1-12 des Vorlesungsskripts)
-
Fr., 15.04.05:
Abschnitt 1.2: Einführung in die
Komplexitätstheorie. Einführung des verwendeten
Turing-Maschinen-Modells, sowie der wichtigsten
Komplexitätsklassen und der von ihnen gebildeten
Hierarchie. Reduktionen und Vollständigkeit.
(Seiten 13-22 des Vorlesungsskripts)
Übungsblatt 1 ausgeteilt.
Anmerkung: Der hier begonnene und am Mittwoch
fortgesetzte Abschnitt über Komplexitätstheorie soll
Ihnen nur einen Überblick über einige wichtige
Ergebnisse der Komplexitätstheorie geben, sowie Ihnen ein
Gefühl für Komplexitätsklassen und ihre
Anordnung vermitteln. Sie brauchen die einzelnen Sätze, deren
Beweise größtenteils auch nicht gegeben werden, nicht im
einzelnen zu verstehen.
-
Mi., 20.04.05:
Abschluss der Einführung in die
Komplexitätstheorie (Abschnitt 1.2).
Beginn des Abschnitts 1.3 über die
Komplexität der Logik erster Stufe und den Satz von
Trachtenbrot: Komplexität des Auswertungsproblems für FO
(Seiten 23-32 des Vorlesungsskripts)
-
Fr., 22.04.05:
Beweis des Satzes von Trachtenbrot.
Anwendung des Satzes von Trachtenbrot: Beweis, dass es nicht entscheidbar ist, ob
ein FO-Satz ordnungsinvariant auf allen endlichen Strukturen ist.
Beginn mit Kapitel 2: Deskriptive Komplexität. Begriff des
Beschreibens von Komplexitätsklassen
eingeführt. Logik zweiter Stufe (SO) definiert.
(Seiten 33-40 des Vorlesungsskripts)
Übungsblatt 2 ausgeteilt.
-
Mi., 27.04.05:
Beispiele für SO-Formeln; Beweis des Satzes von Fagin.
(Seiten 41-51 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 41-49, bis direkt vor Theorem 2.9, behandelt.)
-
Fr., 29.04.05:
Satz von Cook (NP-Vollständigkeit des aussagenlogischen Erfüllbarkeitsproblems) bewiesen.
mit Abschnitt 2.2: "Fixpunktlogiken zur Beschreibung von P und PSPACE" angefangen und Satz von
Knaster und Tarski bewiesen.
(Seiten 51-58 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 49-54 behandelt.)
Übungsblatt 3 ausgeteilt.
-
Mi., 04.05.05:
Kleinste Fixpunktlogik und inflationäre Fixpunktlogik
eingeführt und anhand
von Beispielen illustriert.
Partielle Fixpunkte eingeführt.
(Seiten 55-64 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 55-62, bis direkt vor Beispiel 2.41, behandelt.)
Korrektur von Definition 2.26: Eine Formel phi(R,x) heißt positiv
(bzw. negativ) in R, falls Atome der Form R(y) in phi stets im Bereich
einer geraden (bzw. ungeraden) Anzahl von Negationssymbolen
vorkommen und in phi kein Implikationspfeil "->" und
kein Biimplikationspfeil "<->" vorkommt.
-
Fr., 06.05.05:
Partielle Fixpunktlogik eingeführt und anhand eines Beispiels illustriert.
Beweis des Satzes von Immerman und Vardi (LFP beschreibt PTIME auf geordneten endlichen Strukturen).
(Seiten 65-70 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 62-68, bis direkt vor Satz 2.51, behandelt.)
Übungsblatt 4 ausgeteilt.
-
Mi., 11.05.05:
Die PSPACE-Vollständigkeit der kombinierten Komplexität des Auswertungsproblems für FO bewiesen.
Transitive Hüllenlogik TC definiert und
anhand von Beispielen illustriert. Die Varianten DTC, posTC und posDTC eingeführt.
Bewiesen, dass posDTC genauso ausdrucksstark ist wie DTC.
(Seiten 69-76 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 68-75 behandelt.)
-
Fr., 13.05.05:
Bewiesen, dass LOGSPACE und NLOGSPACE auf endlichen geordneten Strukturen von den Logiken
posDTC und posTC beschrieben werden. Bewiesen, dass posTC auf endlichen geordneten Sturkturen genauso
ausdrucksstark wie TC ist.
(Daraus folgt dann direkt der Satz von Immerman und Szelepcsényi, der besagt, dass
NLOGSPACE abgeschlossen ist unter Komplementbildung.)
(Seiten 77-82 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 76-81, bis direkt vor Theorem 2.67, behandelt.)
Übungsblatt 5 ausgeteilt.
-
Mi., 10.05.05:
Interpretationen und logische Reduktionen behandelt und anhand von Beispielen illustriert.
Gezeigt, wie man jede Struktur (über einer beliebigen Signatur) durch einen ungerichteten Graphen
repräsentieren kann. Damit ist Kapitel 2 (Deskriptive Komplexität) abgeschlossen.
(Seiten 83-90 des Vorlesungsskripts ausgeteilt. In der Vorlesung wurden
heute die Seiten 81-90 behandelt.)
-
Fr., 20.05.05:
Beginn mit Kapitel 3: Ehrenfeucht-Fraisse Spiele. Das m-Runden EF-Spiel eingeführt und anhand von Beispielen
illustriert. Bewiesen, dass Duplicator genau dann eine Gewinnstrategie im m-Runden EF-Spiel auf zwei
linearen Ordnungen hat, wenn die beiden linearen Ordnungen die gleiche Länge oder beide eine Länge größer als
2^m haben.
(Seiten 91-100 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 91-97, bis direkt vor Abschnitt 3.1.3. "Der Satz von Ehrenfeucht", behandelt.)
Übungsblatt 6 ausgeteilt.
-
Mi., 25.05.05:
Beweis des Satzes von Ehrenfeucht und einiger Folgerungen.
(Seiten 97-104 des Vorlesungsskripts ausgeteilt. In der Vorlesung wurden
heute die Seiten 97-101, bis zum Ende von Abschnitt 3.1.3, behandelt.)
-
Fr., 27.05.05:
Beweis des Satzes von Fraisse. Vorarbeiten zum Satz von Hanf.
(Seiten 105-109 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 97-104 behandelt.)
Übungsblatt 7 ausgeteilt.
