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.