Hans-Georg Eßer

esser@pool.informatik.rwth-aachen.de  Aachen, 01.10.1996

Diplomprüfung im Vertiefungsfach Mathematik über Komplexitätstheorie, Mathematische Logik und Graphentheorie bei Prof. Dr. E. Grädel am 30.09.1996

Prüfungsprotokoll

Das folgende Prüfungsprotokoll ist recht kurz und sicherlich unvollständig. Zur Prüfungsatmosphäre möchte ich noch festhalten, daß Herr Grädel während der gesamten Prüfung sehr freundlich und beruhigend war; er ließ mir immer etwas Zeit für die Antwort, so daß ich mich nie unter Druck gesetzt fühlte. Außerdem habe ich viele Hilfestellungen bekommen, wenn ich eine Antwort nicht direkt geben konnte oder mir ein Begriff nicht ganz klar war.

Folgende Texte waren Prüfungsstoff:

• Komplexitätstheorie

– E. Grädel: Vorlesung Komplexitätstheorie, WS 1995/96, V4 Ü2

• Graphentheorie

– L. Volkmann: Graphen und Digraphen, Eine Einführung in die Graphentheorie, 1991, Springer Verlag, Kapitel 1-5 (Inhalt der Vorlesung Graphentheorie I, V3 Ü1, SS 1995)

– D. Jungnickel: Graphen, Netzwerke und Algorithmen, 3. Auflage 1994, BI Verlag, Kapitel 5, 6 (Der Greedy-Algorithmus, Flüsse, S. 169-261)

• Mathematische Logik

– E. Grädel: Vorlesung Mathematische Logik, WS 1993/94, V3 Ü1

– H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, 3. Auflage 1992, BI Verlag, Kapitel XIII (Die Sätze von Lindström)

Nun zum Inhalt der Prüfung:

Mathematische Logik Die Prüfung begann mit einem etwas über 20-minütigen Teil zur Mathematischen Logik. Als erstes bat mich Herr Grädel, den Sequenzenkalkül zu beschreiben. Ich erzählte allgemein etwas über die Idee, die (semantische) Folgerungsbeziehung durch einen Kalkül, also ein System von syntaktischen Regeln, zu beschreiben. Erklärung der Begriffe Sequenz, korrekte Sequenz sowie Korrektheit des Sequenzenkalküls. Beweis des Vollständigkeitssatzes (Terminterpretation, Äquivalenzrelation auf Termuniversum).

Satz von Löwenheim-Skolem und Endlichkeitssatz. Umformulierungen des Endlichkeitssatzes. Um eine Anwendung des Endlichkeitssatzes zu konstruieren, stellte Herr Grädel folgende Aufgabe: Eine Funktion f : X → Y heißt konfluent, wenn es zu jedem a, b ∈ X natürliche Zahlen n und m gibt, so daß f^{n}(a) = f^{m}(b). (Dabei sei f^{n}(a) = f(f(...(f(a))...), n-mal f anwenden) Zeige: es gibt keine Formelmenge Φ der Prädikatenlogik, die ausdrückt, daß f konfluent ist. Benutze dazu den Endlichkeitssatz. Dazu gab Herr Grädel noch den Tip, eine solche Menge Φ zu betrachten, und dann die Menge Φ ∪ {f^{n}(x) ≠ f^{m}(y) | n, m ∈ ℕ} mit zwei Variablen x, y zu bilden. Offensichtlich ist diese Menge nicht erfüllbar, aber jede endliche Teilmenge → Widerspruch Zu den Sätzen von Lindström: was ist ein logisches System (Beispiele), reguläres logisches System. Erster Satz von Lindström. Habe ich nur sehr allgemein erklärt. Mit diesem Thema wurde der Logik-Teil beendet.

Komplexitätstheorie Deterministische Komplexitätsklassen; Einordnen von REG=DSpace(1), DSpace(log n), DSpace(n) – Inklusionen echt? → Platzhierarchiesatz 2-F ist in NLogSpace (was ist eine Färbung; 2-Färbbarkeit äquivalent dazu, daß der Graph bipartit ist; äquivalent dazu, daß es keine Zykel ungerader Länge gibt) Daher Beweis wie folgt möglich: Co-2-F ist ist NLogSpace, da nichtdeterm. nach einem Zykel ungerader Länge gesucht werden kann. Nach dem Satz von Immerman-Szelepcsenyi ist Co-NLogSpace=NLogSpace (Formulierung und Beweisskizze dieses Satzes; irrtumfreies nichtdeterministisches Entscheidungs-/ Berechnungsverfahren), also auch 2-F in NLogSpace. P-vollständig – Achtung: natürlich nicht bzgl. polynomialer Reduktion (Begriff würde ja keinen Sinn ergeben) sondern z.B. bzgl. logspace-Reduktion. NP-vollständige Probleme; 3-F, warum folgt daraus die NP-Vollständigkeit von k-F für alle k > 3? polynomiale Hierarchie: Definition, Inklusionen, Bedingung für das Kollabieren dieser (Σ_{k}^{p} = Σ_{k+1}^{p} für ein k bzw. PH=PSpace, Beweis)

Graphentheorie Es gab keinen gesonderten Prüfungsteil über dieses Thema. Stattdessen wurde während des Komplexitäts-Teils näher auf einige graphentheoretische Probleme eingegangen: Flüsse: Definition von Netzwerk (Kapazität) und Fluß, Algorithmus von Ford-Fulkerson, MaxFlow-MinCut-Theorem

Ende der Prüfung Zum Schluß der Prüfung fragte Herr Grädel noch, ob ich mich mit einem bestimmten Thema besonders gut auskenne und dazu etwas sagen möchte. Tip: vorher über sowas nachdenken – mir ist leider spontan nichts eingefallen...