Dozent: Amin Coja-Oghlan
Termine
Beginn der Vorlesung: 15.04.2004| VL | Dienstag | 09:00 - 11:00 | (RUD 26, 0.313) |
|---|---|---|---|
| Donnerstag | 09:00 - 11:00 | (RUD 26, 0.313) | |
| UE | Donnerstag | 11:00 - 13:00 | (RUD 26, 0.313) |
Zuordnung
- Hauptstudium, 2. Teil eines Kurses
- Theoretische Informatik
Voraussetzungen
- Grundstudium
- Die Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.
Inhalte und Lernziele
Hauptgegenstand der Vorlesung ist das PCP-Theorem ("Probabilistically Checkable Proofs"), welches eines der bedeutendsten juengeren Resultate der Theoretischen Informatik ist, und seine Anwendungen. Das PCP-Theorem zeigt - intuitiv gesprochen - wie man einen mathematischen Beweis (z.B. dass ein bestimmter Graph 3-faerbbar ist, oder dass eine bestimmte SAT-Formel erfuellbar ist) pruefen kann (fast) ohne ihn zu lesen, sofern der Beweis in geeigneter Form aufgeschrieben ist. Das Pruefen des Beweises erfolgt mit probabilistischen Methoden.
Aus dem PCP-Theorem kann hergeleitet werden, dass fuer eine Reihe fundamentaler kombinatorischer Probleme keine guten Algorithmen existieren (es sei denn, P=NP). So ist etwa der triviale Algorithmus fuer Graphenfaerbung, der jedem Knoten eine eigene Farbe gibt, im wesentlichen bestmoeglich. In der Vorlesung werden wir aehnliche Aussagen fuer eine Reihe weiterer Probleme kennenlernen und aus dem PCP-Theorem herleiten, etwa fuer
- das Cliquenproblem,
- das aussagenlogische Erfuellbarkeitsproblem SAT,
- das MAX CUT-Problem.
Obwohl das PCP-Theorem verwendet wird, um zu zeigen, dass es gewisse
Algorithmen nicht gibt, beruht gerade der Beweis des Theorems auf interessanten
Algorithmen.
Insbesondere effiziente algorithmische Techniken, um zu pruefen, ob ein Eingabegraph eine
gewisse Eigenschaft hat oder nicht, ohne den Eingabegraphenen vollstaendig anzusehen,
sind auch unabhaengig von der PCP-Theorie von Bedeutung.
Ebenso werden probablistische Methoden behandelt, die in der
theoretischen Informatik vielfache Anwendung gefunden haben.
Empfohlene Literatur
- Skript zur Vorlesung
- , Proof verifictation and the hardness of approximation problems, J. ACM 45 (1998) 501-555:
- , Einführung in Graphen und Algorithmen
- , Some optimal inapproximability results, J. ACM 48 (2001) 798-859
- , Clique is hard to approximate within n to the power of one minus epsilon, Acta Mathematica 182 (1999) 105-142
- , Graphen und Algorithmen 1
- , Graphen und Algorithmen 2
- , Probabilistically checkable proofs and their consequences for approximation algorithms.
- , A parallel repetition theorem, SIAM J. Comput. 27 (1998) 763-803
English