Logbuch: Logik und Komplexität - Endliche Modelltheorie

Vorlesung im SoSe 2014

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.

Di, 15.04.2014

Eröffnungsveranstaltung. Klärung von Organisatorischem.
"Kapitel 0: Einleitung": Einführung ins Thema durch Beispiele von Formeln der Logik zweiter Stufe ("3-Färbbarkeit"), Transitive-Hüllen-Logik ("Erreichbarkeit") und Fixpunktlogik ("Erreichbarkeit").
Start mit "Kapitel 1: Grundlagen": grundlegende Notationen, Turingmaschinen, der Satz von Trakhtenbrot

Material:: handschriftliche Notizen zu Kapitel 0 und handschriftliche Notizen zu Kapitel 1
Skript [S]: Kapitel 0, Kapitel 1.1, Kapitel 1.2.1, Kapitel 1.3.4
Weitere Lektüre:: Lehrbuch [L]: Kapitel 1, Kapitel 2.1 und Kapitel 9.1

Di, 22.04.2014

Abschluss von "Kapitel 1: Grundlagen": Beweis des Satzes von Trakhtenbrot
Start mit "Kapitel 2: Die Logik zweiter Stufe (SO)": Syntax und Semantik von SO, Beispiele für SO-Formeln, Definition von MSO, EMSO und ESO, Vorarbeiten zum Satz von Büchi

Material:: handschriftliche Notizen zu Kapitel 2 (Teil 1: Definition und Beispiele zu SO und MSO)
Skript: Kapitel 1.3.4, Kapitel 2.1.1
Lehrbuch [L]: Kapitel 7.1, Kapitel 1.3, Kapitel 2.2 und Kapitel 7.4

Di, 29.04.2014

Weiter mit "Kapitel 2: Die Logik zweiter Stufe (SO)": Beweis des Satzes von Büchi, Anwendung des Satzes von Büchi (logische Reduktion zum Nachweis, dass "Hamiltonkreis" nicht MSO-definierbar ist)

Material:: handschriftliche Notizen zu Kapitel 2 (Teil 2: Der Satz von Büchi)
Weitere Lektüre:: Lehrbuch [FG]: Kapitel
Lehrbuch [L]: Kapitel 7.4

Do, 08.05.2014

Weiter mit "Kapitel 2: Die Logik zweiter Stufe (SO)": Logische Beschreibung von Komplexitätsklassen, die Standardkodierung von Strukturen, der Satz von Fagin, Beweis der "leichten" Richtung des Satzes von Fagin, Vorarbeiten zum Beweis der "schweren" Richtung des Satzes von Fagin

Material:: handschriftliche Notizen zu Kapitel 2 (Teil 3: Der Satz von Fagin; heute: Seiten 40-49)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 9.2

Di, 13.05.2014

Weiter mit "Kapitel 2: Die Logik zweiter Stufe (SO)": Abschluss des Beweises des Satzes von Fagin; Beweis des Satzes von Cook und Levin (NP-Vollständigkeit des aussagenlogischen Erfüllbarkeitsproblems) unter Verwendung des Satzes von Fagin

Material:: handschriftliche Notizen zu Kapitel 2 (Teil 4: Der Satz von Fagin und der Satz von Cook und Levin; heute: Seiten 48-59)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 9.2

Di, 20.05.2014

Weiter mit "Kapitel 2: Die Logik zweiter Stufe (SO)": Horn-Formeln; der Satz von Grädel (logische Charakterisierung von P auf der Klasse aller endlichen geordneten Strukturen durch ESO-HORN-Sätze); Ehrenfeucht-Fraisse Spiele für Fragmente der Logik zweiter Stufe; das Ajtai-Fagin Spiel für EMSO.

Material:: handschriftliche Notizen zu Kapitel 2 (Teil 5: Satz von Grädel und EF-Spiele für Fragmente der Logik zweiter Stufe; heute: Seiten 60-77)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 9.2 und 7.1-7.3

Do, 22.05.2014

Abschluss von "Kapitel 2: Die Logik zweiter Stufe (SO)": Satz von Hanf (hier ohne Beweis), Anwendung des Ajtai-Fagin Spiel für EMSO: Beweis des Satzes von Fagin, der besagt, dass Graphzusammenhang nicht EMSO-definierbar ist.
Start mit "Kapitel 3: 0-1-Gesetze": Einführung des Begriffs der asymptotischen Wahrscheinlichkeit; Beispiele: Berechnung der asymptotischen Wahrscheinlichkeit der Probleme EVEN ("Hat das Universum gerade Kardinalität?"), PARITY ("Enthält eine Relation gerade viele Tupel?"), ISOLATED-NODES ("Besitzt ein Graph isolierte Knoten?").

Material:: handschriftliche Notizen zu Kapitel 2 (Teil 6: Satz von Hanf und Anwendung des Ajtai-Fagin-Spiels; heute: Seiten 78-85) und handschriftliche Notizen zu Kapitel 3 (Teil 1: Asymptotische Wahrscheinlichkeiten; heute: Seiten 86-90)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 7.3 und Kapitel 12.1

Di, 27.05.2014

Weiter mit "Kapitel 3: 0-1-Gesetze": Berechnung der asymptotischen Wahrscheinlichkeit von GRAPH-ZUSAMMENHANG; Einführung des Begriffs "eine Logik L besitzt das 0-1-Gesetz bzgl. einer Klasse S von Strukturen"; Nachweis des Satzes von Glebskii et al. und Fagin, der besagt, dass FO das 0-1-Gesetz bzgl. der Klasse UG aller ungerichteten Graph besitzt (dazu wurden betrachtet: Erweiterungsaxiome für ungerichtete Graphen), und dass FO das 0-1-Gesetz bzgl. der Klasse aller σ-Strukturen (für jede endliche relationale Signatur σ) besitzt (dazu wurden eingeführt: Erweiterungsaxiome für σ-Strukturen).

Material:: handschriftliche Notizen zu Kapitel 3 (Teil 2: 0-1-Gesetze für FO; heute: Seiten 91-111)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 12.1 und 12.2

Di, 10.06.2014

Weiter mit "Kapitel 3: 0-1-Gesetze": Der Rado-Graph; Nachweis, dass jeder abzählbare Graph, der sämtliche Erweiterungsaxiome erfüllt, isomorph zum Rado-Graphen ist; Entscheidbarkeit der FO-Theorie des Rado-Graphen; Berechenbarkeit der asymptotischen Wahrscheinlichkeit von FO-Sätzen auf ungerichteten Graphen; infinitäre Logik und deren k-Variablen Fragment

Material:: handschriftliche Notizen zu Kapitel 3 (Teil 3: 0-1-Gesetze für FO; heute: Seiten 112-121 und Seiten 111-114 im Skript [S])
Weitere Lektüre:: Lehrbuch [L]: Kapitel 12.3, 8.2 und 11.1

Do, 12.06.2014

Abschluss von "Kapitel 3: 0-1-Gesetze": Pebble-Spiele (Spielregeln, Beispiele), Zusammenhang zwischen k-Pebble-Spielen und Definierbarkeit in infinitärer k-Variablen-Logik; Nachweis des Satzes von Kolaitis und Vardi, der besagt, dass die infinitäre Logik mit endlich vielen Variablen das 0-1-Gesetz bzgl. der Klasse UG und bzgl. der Klasse aller Strukturen über einer endlichen relationalen Signatur besitzt; Anwendung des 0-1-Gesetzes; Anwendung von Pebble-Spielen zum Nachweis des Satzes von de Rougemont, der besagt, dass HAMILTONKREIS nicht in infinitärer Logik mit endlich vielen Variablen definiert werden kann.

Material:: handschriftliche Notizen zu Kapitel 3 (Teil 4: Pebble-Spiele und 0-1-Gesetze für infinitäre Logiken)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 12.3, 8.2 und 11.2

Di, 17.06.2014

Start mit "Kapitel 4: Fixpunktlogiken": Grundbegriffe zum Thema "Fixpunkte", der Satz von Knaster und Tarski, Syntax und Semantik der kleinsten Fixpunktlogik (LFP), Beispiele für LFP-Formeln

Material:: handschriftliche Notizen zu Kapitel 4 (Teil 1: Die kleinste Fixpunktlogik)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 10.1 und 10.2

Di, 01.07.2014

Weiter mit "Kapitel 4: Fixpunktlogiken": Syntax und Semantik der inflationären Fixpunktlogik (IFP) und der partiellen Fixpunktlogik (PFP); Beispiele für IFP- und für PFP-Formeln; Einbettung von PFP in infinitäre Logik mit endlich vielen Variablen; Transfer der Nicht-Ausdrückbarkeitsresultate für infinitäre Logik mit endlich vielen Variablen zu Nicht-Ausdrückbarkeitsresultaten für Fixpunktlogiken

Material:: handschriftliche Notizen zu Kapitel 4 (Teil 2: Inflationäre Fixpunktlogik, partielle Fixpunktlogik und infinitäre Logik mit endlich vielen Variablen)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 10.1 und 10.2

Di, 08.07.2014

Weiter mit "Kapitel 4: Fixpunktlogiken": Beweis der Sätze von Immerman und Vardi ("LPF bzw IFP beschreiben PTIME auf der Klasse aller endlichen geordneten Strukturen" und "PFP beschreibt PSPACE auf der Klasse aller endlichen geordneten Strukturen"); Verwendung der logischen Charakterisierung von PSPACE durch PFP zum Nachweis, dass die kombinierte Komplexität des Auswertungsproblems für FO PSPACE-vollständig ist (Beginn des Beweises)

Material:: handschriftliche Notizen zu Kapitel 4 (Teil 3: Fixpunktlogiken und Komplexitätsklassen - Seiten 151 bis 157)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 10.4

Do, 10.07.2014

Abschluss von "Kapitel 4: Fixpunktlogiken": Verwendung der logischen Charakterisierung von PSPACE durch PFP zum Nachweis, dass die kombinierte Komplexität des Auswertungsproblems für FO PSPACE-vollständig ist (Abschluss des Beweises);
Rückblick auf die wichtigsten Themenbereiche, die im Laufe des Semesters in Vorlesung und Übung behandelt wurden; Ausblick auf weiterführende Themen im Bereich "Logik und Komplexität" bzw. "Endliche Modelltheorie".

Material:: handschriftliche Notizen zu Kapitel 4 (Teil 3: Fixpunktlogiken und Komplexitätsklassen - Seiten 157 bis 159)
Weitere Lektüre:: Lehrbuch [L]: Kapitel 10.4