Institut für Theoretische Informatik, Algorithmik

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

  1. Ausiello et al.: Complexity and Approximation, Springer 1999.
  2. Juraj Hromkovic: Theoretische Informatik, Teubner 2007.
  3. Richard Ladner: On the Structure of Polynomial Time Reducibility.
  4. Nash et al.: Universal Languages and the Power of Diagonalization.
  5. Adi Shamir: IP=PSPACE.
  6. Uwe Schöning: Perlen der Theoretischen Informatik, BI Wissenschaftsverlag 1995.
  7. Ingo Wegener: Komplexitätstheorie, Springer 2003.
  8. Avi Wigderson: P, NP and mathematics - a computational complexity perspective, 2006.