Proseminar: Die P-ungleich-NP-Vermutung (SS 2015)
Allgemeines
Betreuung
Dr. Moritz Baum, Dr. Thomas Bläsius, Dr. Fabian Fuchs, Dr. Michael Hamann, Dr. Tanja Hartmann, Dr. Benjamin Niedermann, Dr. Roman Prutkin, Dr. Ignaz Rutter, Dr. Franziska Wegner, Dr. Tobias Zündorf
Anmeldung
Die Teilnehmerzahl ist beschränkt, die Plätze werden nach Anmeldereihenfolge vergeben. Anmeldung bitte per Mail bei Dr. Ignaz Rutter.
Die maximale Teilnehmerzahl ist hiermit erreicht. Sie können Sich jedoch gerne auf die Warteliste setzen lassen.
Regelmäßiger Termin
Mittwochs um 9:45 im SR -119 (Informatikgebäude)
Vorbesprechung am 15. April
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.
Eine Übersicht findet sich auf den Einführungsfolien.
Aktuelles
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.
| Termin | Betreuung | Thema | Studenten |
|---|---|---|---|
| 06.05. | Franziska | Kurze Wiederholung der schon bekannten Dinge (Klassen P, NP, NP-Competeness, Reduktion usw.), die Klassen coNP, EXP und NEXP, weitere Gedankenexperimente „Was wäre wenn…?“, untere Schranken für die Länge von Resolutionsbeweisen als Hinweis auf NP ungleich coNP | Adrian, Florian |
| 13.05. | Tanja | Diagonalisierung als Beweistechnik (z.B. für die Existenz echter Time-Complexity-Hierarchien und die Existenz von nicht NP-vollständigen Sprachen in NP\P) sowie die Grenzen dieser Beweistechnik in Bezug auf die Frage P ungleich NP?, Vorstellung der polynomiellen Hierarchie | Corvin, Matthias |
| 20.05. | Fabian | Space Complexity: Die Klasse PSPACE und ihr Verhältnis zu P und NP, Gemeinsamkeiten und Unterschiede zwischen Time- und Space Complexity | Raphael, Valentin |
| 27.05 | Thomas | Boolean Circuits: Ein alternatives Modell zur Turingmaschine, daraus resultierende Komplexitätsklassen und deren Verhältnis zu P und NP, Bedeutung des Modells für die Frage P ungleich NP? | Matthias G., Saskia |
| 03.06. | Ignaz | Circuit lower bounds: Die Klassen AC0 und ACC0, Hastad's Switching Lemma und die Erkenntnis, dass es bereits einfache Funktionen ohne polynomielle Circuits gibt | Souhail, Yassine |
| 10.06. | Tobias | Randomisierung und Derandomisierung: Probabilistische Turingmaschinen, daraus resultierende Komplexitätsklassen, deren Zusammenhang mit Boolean Circuits und die Konzequenzen für die Frage P ungleich NP? | Nicolai, Christian |
| 17.06. | Michael | Interaktive Beweise: Interagierende Beweiser und probabilistische Verifizierer, die Klassen IP und AM und die besondere Rolle des Graph-Isomorphie-Problems | Nicolas |
| 24.06. | Ignaz | Das PCP-Theorem und Approximation: Probabilistic Checkable Proofs und deren Bedeutung für die Suche nach guten Approximationen | Oliver, Johannes |
| 01.07. | Benjamin | Komplexität von Zählproblemen: Die Klasse #P, Zusammenhänge zwischen P, NP und #P und weiteren Klassen | Dennis, Stefan |
| 08.07. | Moritz | Entscheidungsbäume: Ein einfacheres Modell als TMs, Verhalten der resultierenden Komplexitätsklassen, Yao's Min-Max-Lemma als Instrument zur Bestimmung unterer Komplexitätsschranken randomisierter Algorithmen | Benedict |
| 15.07. | Roman | Average Case Complexity: Die Klassen distP und distNP (analog zu P und NP) und der Satz von Levin zur Existenz eines distNP-vollständigen Problems | Akin, Tobias |
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.