-
Mo, 16.04.2007:
Organisatorisches sowie Kapitel 0: Einleitung und Kapitel 1.1: Logik erster Stufe (FO)
Seiten 1-14 des Vorlesungsskripts ausgeteilt.
-
Mi, 18.04.2007:
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 15-22 des Vorlesungsskripts ausgeteilt.
Übungsblatt 1 ausgeteilt.
Anmerkung: Der hier begonnene und am nächsten Montag
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 hier auch nicht gegeben werden, nicht im
einzelnen zu verstehen.
-
Mo, 23.04.2007:
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
Trakhtenbrot: Komplexität des Auswertungsproblems für FO
Seiten 23-34 des Vorlesungsskripts ausgeteilt.
Korrektur: Proposition 1.45 besagt folgendes: Für jedes k>=0 gilt:
\Sigma^p_{k+1} = NP^{\Pi^p_k} = NP^{\Sigma^p_k}.
-
Mi, 25.04.2007:
Beweis des Satzes von Trakhtenbrot.
Anwendung des Satzes von Trakhtenbrot: Beweis, dass es nicht entscheidbar ist, ob
ein FO-Satz ordnungsinvariant auf allen endlichen Strukturen ist.
Seiten 35-44 des Vorlesungsskripts ausgeteilt.
Übungsblatt 2 ausgeteilt.
-
Mo, 30.04.2007:
Beginn von Kapitel 2: Deskriptive Komplexität. Begriff des
Beschreibens von Komplexitätsklassen
eingeführt. Logik zweiter Stufe (SO) definiert.
Beispiele für SO-Formeln. Beginn des Beweises des Satzes von Fagin.
Seiten 45-52 des Vorlesungsskripts ausgeteilt.
-
Mi, 02.05.2007:
Abschluss des Beweises des Satzes von Fagin.
Satz von Cook (NP-Vollständigkeit des aussagenlogischen Erfüllbarkeitsproblems) unter Verwendung
des Satzes von Fagin bewiesen.
Mit Abschnitt 2.2: "Fixpunktlogiken zur Beschreibung von P und PSPACE" angefangen und Satz von
Knaster und Tarski bewiesen.
Seiten 53-56 des Vorlesungsskripts ausgeteilt.
Übungsblatt 3 ausgeteilt.
-
Mo, 07.05.2007:
Induktionsstufen und induktive Abbildungen definiert. Die kleinste Fixpunktlogik (LFP)
eingeführt und anhand von Beispielen illustriert.
Seiten 57-64 des Vorlesungsskripts ausgeteilt (in der
Vorlesung wurden heute die Seiten 56-61 bis incl. Beispiel 2.29 behandelt.)
-
Mi, 09.05.2007:
Die inflationäre Fixpunktlogik (IFP) und die partielle Fixpunktlogik (PFP)
eingeführt und anhand von Beispielen illustriert.
Die Datenkomplexität des Auswertungsproblems für LFP, IFP und PFP betrachtet.
Beginn des Beweises des Satzes von Immerman und Vardi (LFP und IFP beschreiben PTIME auf geordneten endlichen Strukturen).
Seiten 65-68 des Vorlesungsskripts ausgeteilt (in der
Vorlesung wurden heute die Seiten 62-67 behandelt.)
Übungsblatt 4 ausgeteilt.
-
Mo, 14.05.2007:
Abschluss des Beweises des Satzes von Immerman und Vardi.
Logische Charakterisierung von PSPACE angegeben (PFP beschreibt PSPACE auf geordneten endlichen Strukturen).
Beginn des Beweises der PSPACE-Vollständigkeit des Auswertungsproblems für FO (bzgl. der kombinierten Komplexität).
Seiten 69-74 des Vorlesungsskripts ausgeteilt.
-
Mi, 16.05.2007:
Rest des Beweises der PSPACE-Vollständigkeit des Auswertungsproblems für FO (bzgl. der kombinierten Komplexität).
Transitive Hüllenlogiken TC, DTC, posTC, posDTC definiert und
anhand von Beispielen illustriert.
Bewiesen, dass posDTC genauso ausdrucksstark ist wie DTC.
Seiten 75-78 des Vorlesungsskripts ausgeteilt.
Übungsblatt 5 ausgeteilt.
-
Mo, 21.05.2007:
Bewiesen, dass LOGSPACE und NLOGSPACE auf endlichen geordneten Strukturen von den Logiken
posDTC und posTC beschrieben werden. Theorem 2.66 bewiesen, d.h. bewiesen, dass posTC auf endlichen geordneten Sturkturen genauso
ausdrucksstark wie TC ist (Schritt 4 des Beweises wird in der nächsten Vorlesungsstunde nachgereicht).
Daraus gefolgert, dass NLOGSPACE auf FinOrd auch durch die Logik TC beschrieben wird.
Dies benutzt, um den Satz von Immerman und Szelepcsényi (NLOGSPACE = co-NLOGSPACE) zu beweisen.
Seiten 79-84 des Vorlesungsskripts ausgeteilt.
-
Mi, 23.05.2007:
Schritt 4 des Beweises von Theorem 2.66 nachgereicht. Überblick über die Inhalte von Kapitel 2 gegeben.
Beginn von Kapitel 3: Ehrenfeucht-Fraissé Spiele. Einige Grundbegriffe wie "Quantorenrang", "m-Äquivalenz" und
"partielle Isomorphismen" geklärt.
Das m-Runden EF-Spiel eingeführt und anhand von Beispielen
illustriert.
Seiten 85-90 des Vorlesungsskripts ausgeteilt.
Übungsblatt 6 ausgeteilt.
-
Mi, 30.05.2007:
Bewiesen, dass Duplicator 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.
Beweis des Satzes von Ehrenfeucht.
Seiten 91-98 des Vorlesungsskripts ausgeteilt. In der Vorlesung wurden
heute die Seiten 90-94 (bis incl. Bemerkung 3.17) behandelt.
Übungsblatt 7 ausgeteilt.
-
Mo, 04.06.2007:
Aus dem Satz von Ehrenfeucht gefolgert, dass es für jede feste Signatur und jede Zahl m nur endlich viele nicht-äquivalente FO-Sätze der
Quantorentiefe m gibt. In Korollar 3.19 die Methode zum Nachweis der Nicht-FO-Definierbarkeit
bestimmter Probleme zusammengefasst und angewendet, um
zu zeigen, dass die Klasse aller linearen Ordnungen gerader Länge nicht FO-definierbar ist. Dies benutzt, um mit der Methode der
logischen Reduktionen zu folgern, dass auch die Klasse aller zusammenhängenden Graphen nicht FO-definierbar ist.
Die Begriffe Gaifman-Graph, r-Nachbarschaft und r-Umgebungstyp eingeführt und den Satz von Hanf bewiesen.
Seiten 99-102 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 94-101 (von Bemerkung 3.18 bis incl. Korollar 3.26) behandelt.
Details zur Methode der logischen Reduktionen können Sie in Kapitel 3.4 nachlesen,
das allerdings nicht
in der Vorlesung behandelt wird und daher auch nicht prüfungsrelevant ist.
-
Mi, 06.06.2007:
Die Hanf-Lokalität der Logik erster Stufe bewiesen und angewendet, um einen alternativen Beweis dafür zu finden, dass
die Klasse aller zusammenhängenden Graphen nicht FO-definierbar ist.
Hin- und Her-Systeme eingeführt, den Satz von Fraissé bewiesen und an einem Beispiel illustriert.
Seiten 103-106 des Vorlesungsskripts ausgeteilt. In der
Vorlesung wurden heute die Seiten 101-105 behandelt.
Übungsblatt 8 ausgeteilt.
-
Mo, 18.06.2007:
Das EF-Spiel für die existentielle Logik zweiter Stufe eingeführt.
Das Ajtai-Fagin-Spiel für die monadische existentielle Logik zweiter Stufe eingeführt.
Beweis des Satzes, dass Graphzusammenhang in monadischer universeller Logik
zweiter Stufe, nicht aber in monadischer existentieller Logik zweiter Stufe
definiert werden kann (Theorem 3.42).
Seiten 107-110 des Vorlesungsskripts ausgeteilt. In der Vorlesung wurden
heute die Seiten 106-110 behandelt.
-
Mi, 20.06.2007:
Abschluss des Beweises von Theorem 3.42.
Einführung der k-Variablen Logik FO^k und der infinitären k-Variablen Logik.
Einige Beispiele für Formeln dieser Logiken.
Beweis, dass zwei endliche Strukturen genau dann dieselben Sätze der infinitären
k-Variablen Logik erfüllen, wenn sie dieselben FO^k-Sätze erfüllen.
Seiten 111-116 des Vorlesungsskripts ausgeteilt. In der Vorlesung wurden
heute die Seiten 110-115 (bis incl. Notation 3.52) behandelt.
Übungsblatt 9 ausgeteilt. Da "Pebble-Spiele" heute noch nicht
eingeführt worden sind, sind von Blatt 9 zunächst lediglich die Aufgaben 1, 2 und 3 zu bearbeiten.
-
Mo, 15.06.2007:
Einführung von Pebble-Spielen.
Einige Beispiele zu Pebble-Spielen. Charakterisierung der
Äquivalenz bzgl. infinitären k-Variablen Formeln durch Pebble-Spiele und durch
k-partielle Isomorphie. Beginn des Beweises von Theorem 3.62, das besagt, dass es keine Formel der infinitären k-Variablen Logik
gibt, die die Klasse aller Graphen, die einen Hamiltonpfad haben, definiert.
Seiten 117-121 des Vorlesungsskripts ausgeteilt.
-
Mi, 27.06.2007:
Abschluss des Beweises von Theorem 3.62.
Beginn von Kapitel 4: Der Satz von Gaifman.
Notationen für r-Nachbarschaften sowie die Begriffe lokale Formeln, basis-lokale Sätze und
Formeln in Gaifman-Normalform eingeführt.
Beginn des Beweises des Satzes von Gaifman (Gaifmans Originalbeweis, der per Induktion über den Formelaufbau vorgeht).
Seiten 131-138 des Vorlesungsskripts ausgeteilt.
Übungsblatt 10 ausgeteilt.
-
Mo, 02.07.2007:
Abschluss des Beweises des Satzes von Gaifman.
Anwendungen des Satzes von Gaifman vorgestellt: (1) Die Gaifman-Lokalität der Logik erster Stufe, die es erlaubt,
für viele konkrete Anfragen zu zeigen, dass sie nicht FO-definierbar sind.
(2) "Algorithmische Meta-Theoreme", die besagen, dass das Auswertungsproblem für FO auf bestimmten Klassen von
Strukturen in Linearzeit (Datenkomplexität) gelöst werden kann — hier: Beweis des Satzes von Seese, der besagt, dass das
Auswertungsproblem für FO auf Klassen von Graphen von beschränktem Grad in Linearzeit (Datenkomplexität) gelöst werden kann.
Seiten 139-144 des Vorlesungsskripts ausgeteilt.
-
Mi, 04.07.2007:
Eine nicht-elementare untere Schranke an die Länge von Formeln in Gaifman-Normalform bewiesen.
Genauer: Gezeigt, dass es für jede Zahl h eine FO-Formel der Länge O(h^4) gibt, so dass
jede dazu äquivalente Formel in Gaifman-Normalform die Länge Turm(h) hat, wobei
Turm(h) induktiv definiert ist durch Turm(0)=1 und Turm(h+1)=2^{Turm(h)}.
Seiten 145-152 des Vorlesungsskripts ausgeteilt.
Übungsblatt 11 ausgeteilt.
-
Mo, 09.07.2007:
Beginn von Kapitel 5: Fixpunktlogiken. Beweis, dass jede PFP-Formel zu einer
Formel der infinitären k-Variablen Logik äquivalent ist.
Simultane Fixpunkte und die Logik S-LFP eingeführt und anhand von Beispielen illustriert.
Seiten 153-158 des Vorlesungsskripts ausgeteilt.
-
Mi, 11.07.2007:
Gezeigt, dass S-LFP und LFP dieselbe Ausdrucksstärke besitzen.
Gezeigt, dass S-IFP und IFP dieselbe Ausdrucksstärke besitzen.
Die Stage-Comparison-Relationen eingeführt.
Seiten 159-164 des Vorlesungsskripts ausgeteilt.
Übungsblatt 12 ausgeteilt.
-
Mo, 16.07.2007:
Gezeigt, dass die Stage-Comparison-Relationen in IFP und in LFP definiert werden können.
Den Satz von Gurevich und Shelah (IFP = LFP auf Fin) bewiesen.
Seiten 163-168 des Vorlesungsskripts ausgeteilt.
-
Mi, 18.07.2007:
Zusammenfassung der wichtigsten Inhalte der Vorlesung.
Titelseite und Inhaltsverzeichnis des Vorlesungsskripts ausgeteilt.
