Proseminar: Die P-ungleich-NP-Vermutung (SS 2012)
Allgemeines
Betreuung
Dr. Moritz Baum, Dr. Thomas Bläsius, Dr. Fabian Fuchs, Dr. Tanja Hartmann, Dr. Ignaz Rutter, Dr. Markus Völker, Prof. Dr. Dorothea Wagner
Regelmäßiger Termin
Seminarvorträge Freitag, 11:30-13:00, erstmals am 11. Mai
Ort HS -101, Informatikgebäude
Inhalt
Die P-ungleich-NP-Frage ist eines der größten ungelösten Probleme der Informatik. Das Proseminar behandelt aktuelle Ansätze zur Lösung der P-ungleich-NP-Frage. Ziel ist, dass die Teilnehmer in Zweiergruppen einen dieser Ansätze erarbeiten und anschließend in einem 1,5-stündigen Vortrag vorstellen. Eine Ausarbeitung muss nicht angefertigt werden.
Aktuelles
- 2. Februar: Anmeldungen zum Proseminar sind nun möglich. Bitte schreibt dazu eine Mail mit Namen und Matrikelnummer an Dr. Tanja Hartmann
- 20. April um 9.45 Uhr: Vorbesprechung in Raum 301, Informatikhauptgebäude.
Themen
Der Inhalt orientiert sich am Buch „Computational Complexity: A Modern Approach“ von Sanjeev Arora und Boaz Barak. Eine Vorversion des Buches ist im Netz frei verfügbar. – Die endgültige Buchversion hat sich gegenüber dieser jedoch in einigen Bereichen stark verändert. In der Informatik-Bibliothek gibt es ein Präsenzexemplar. Die einzelnen Kapitel sollen durch den Bezug zu anderen Veröffentlichungen zu spezialiserten Themen ergänzt werden.
- NP-vollständigkeit, Zeit-Hierarchie, polynomielle Hierarchie, Graph-Isomorphie und NPI (Kap. 3)
- Space-Complexity, Savitch's Theorem, PSPACE-completeness (Kap. 4) Folien
- Boolean Circuits (Kap. 6) Folien
- Randomisierung (Kap. 7), und Derandomisierung (Kap. 20)
- Untere Schranken, Entscheidungsbäume, Yaos Min-Max-Lemma (Kap. 12) Folien
- Average-Case Complexity, Smoothed Analysis (Kap. 18) Folien, Beweis Satz von Levin
- PCP-Theorem und Approximationsschranken (Kap. 11)
Termine
Die Vorbesprechung findet am Freitag, den 20. April um 9.45 Uhr im Raum 301, Informatikhauptgebäude statt. An diesem Termin werden die Themen vergeben und die weiteren Termine festgelegt.
Literatur
- Sanjeev Arora und Boaz Barak: Computational Complexity: A Modern Approach, 2009
- Ausiello et al.: Complexity and Approximation, Springer 1999.
- Juraj Hromkovic: Theoretische Informatik, Teubner 2007.
- Richard Ladner: On the Structure of Polynomial Time Reducibility.
- Nash et al.: Universal Languages and the Power of Diagonalization.
- Adi Shamir: IP=PSPACE.
- Uwe Schöning: Perlen der Theoretischen Informatik, BI Wissenschaftsverlag 1995.
- Ingo Wegener: Komplexitätstheorie, Springer 2003.
- Avi Wigderson: P, NP and mathematics - a computational complexity perspective, 2006.