Proseminar: Die P-ungleich-NP-Vermutung (SS 2011)
Allgemeines
Betreuung
Dr. Andrea Kappes, Dr. Andreas Gemsa, Dr. rer. nat. Robert Görke, Dr. Markus Völker, Prof. Dr. Dorothea Wagner
Regelmäßiger Termin
mittwochs 11:30 – 13:00 Uhr, Seminarraum -119 (Informatikgebäude 50.34)
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 Vortrag vorstellen und geeignet zu einer Ausarbeitung zusammenfassen.
Aktuelles
- 13. April: Hier findet ihr die Folien zur Vorbesprechung.
- 11. April: Themen sind online
- 21. März: Anmeldungen zum Proseminar sind noch möglich. Bitte schreibt dazu eine Mail mit Namen und Matrikelnummer an Dr. Andrea Kappes
Themen
- Orakelklassen und die polynomielle Hierarchie (7, Kapitel 10)
- Interaktive Beweise (7, Kapitel 11)
- Die Komplexität von Black-Box-Problemen (7, Kapitel 9)
- Das PCP-Problem und die Komplexität von Approximationsalgorithmen (7 Kapitel 12)
- Speicherplatzbasierte Komplexitätsklassen (7, Kapitel 13)
- IP=PSPACE (6, Kapitel 21)
- Die Komplexität von nichtuniformen Problemen (7, Kapitel 14)
Weitere Themen (je nach Teilnehmerzahl):
- Kolmogorov-Komplexität (6, Kapitel 8)
- Pebble Game (6, Kapitel 24)
- Kommunikationskomplexität (7, Kapitel 15)
Termine
| Datum | Zeit | Ort | Thema |
|---|---|---|---|
| 13.04. | 11:30–13:00 | SR -119 | Vorbesprechung |
| 04.05. | - | - | Abgabe der Folien für den Kurzvortrag |
| 11.05. | 11:30–13:00 | SR -119 | Kurzvorträge |
| 18.05. | 11:30-13:00 | SR -119 | kww-Schulung |
| 25.05. | 11:30–13:00 | SR -119 | Jakob + Marten: Orakelklassen und die polynomielle Hierarchie Lukas + Uwe: Interaktive Beweise |
| 01.06. | 11:30–13:00 | SR -119 | Sarah + Max: Die Komplexität von Black-Box-Problemen Joachim + Fabian: Die Komplexität von nichtuniformen Problemen |
| 08.06. | 11:30–13:00 | SR -119 | Monica + Tobias: Speicherplatzbasierte Komplexitätsklassen Kateryna + Hao: IP=PSPACE |
| 15.06. | 11:30–13:00 | SR -119 | Sabine + Marcel: Das PCP-Problem und die Komplexität von Approximationsalgorithmen |
| 15.07. | - | - | Abgabe der ersten Version der Ausarbeitung |
| 15.08. | - | - | Abgabe der finalen Version der Ausarbeitung |
Literatur
- 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.