Proseminar: Die P-ungleich-NP-Vermutung
Sommersemester 2008
Allgemeines
Betreuung
Regelmäßiger Termin
dienstags 15:45 – 17:15 Uhr, Seminarraum 301 (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 sich jeder Teilnehmer einen dieser Ansätze erarbeitet und anschließend in einem Vortrag vorstellt. Außerdem wird ein kleines Training in Wissenschaftlichem Schreiben und Vortragen angeboten.
Aktuelles
8. Mai: Die Terminzuteilung der Hauptvorträge findet sich hier (Änderungen vorbehalten). Die Reihenfolge der Zwischenvorträge lehnt sich – soweit möglich – an diese Einteilung an.
22. April: Die Einteilung für die kww-Schulung findet sich hier.
Termine
| Datum | Zeit | Ort | Thema |
|---|---|---|---|
| 22.04. | 15:45–17:15 | SR 301 | Vorbesprechung |
| 29.04. | 15:45–17:15 | SR 301 | Fachliches Präsentieren |
| 07.05. | 16:00–19:00 | SR 301 | kww-Schulung |
| 08.05. | 16:00–19:00 | SR 131 | kww-Schulung |
| 13.05. | 15:45–18:00 | SR 301 | Zwischenvorträge |
| 20.05. | 15:45–18:00 | SR 301 | Wiss. Schreiben + LaTeX |
| 27.05. | 15:45–19:00 | SR 301 | Hauptvorträge |
| 04.06. | 14:00–17:15 | SR -109 | Hauptvorträge |
| 15.06. | Gliederung Ausarbeitung |
| 29.06. | erste Fassung Ausarbeitung |
| 20.07. | Hauptfassung Ausarbeitung |
| 03.08. | endgültige Fassung Ausarbeitung |
Einteilung kww-Termine
- 07.05.: Jan, Felix, Florian, Christian, Benjamin
- 08.05.: Stephan, Nelli, Simon, Moritz, Alexander
Vorträge
| Thema | Vortragende | Betreuer |
|---|---|---|
| – | ||
| Dienstag, 27. Mai | ||
| On the Structure of Polynomial-Time Reducibility [3] | Moritz | Reinhard |
| Speicherplatzbasierte Komplexitätsklassen [7, Kap. 13.1–13.4] | Benjamin | Martin |
| Pebble Game [6, Kap. 24] | Christian | Reinhard |
| Interaktive Beweise [7, Kap. 11] | Stephan | Marcus |
| IP=PSPACE [5] | Simon | Marcus |
| – | ||
| Mittwoch, 4. Juni | ||
| Das PCP-Theorem [1, Kap. 7] | Jan | Reinhard |
| Die Komplexität von nichtuniformen Problemen [7, Kap. 14.1–14.5] | Felix | Martin |
| Kommunikationskomplexität [7, Kap. 15.1–15.3] | Nelli | Reinhard |
| Das Äquivalenzproblem für LOOP(1)- und LOOP(2)-Progr. [6, Kap. 3] | Florian | Reinhard |
| Kolmogorov-Komplexität [2, Kap. 2.4/5.6] | Alexander | Marcus |
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.