Institut für Theoretische Informatik, Algorithmik

Proseminar: Die P-ungleich-NP-Vermutung (SS 2011)

Allgemeines

Betreuung

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

  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.