Institut für Theoretische Informatik, Algorithmik

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

Allgemeines

Betreuung

Anmeldung

Die Teilnehmerzahl ist beschränkt, die Plätze werden nach Anmeldereihenfolge vergeben. Anmeldung bitte per Mail bei Dr. Ignaz Rutter.

Die maximale Teilnehmerzahl ist hiermit erreicht. Sie können Sich jedoch gerne auf die Warteliste setzen lassen.

Regelmäßiger Termin

Mittwochs um 9:45 im SR -119 (Informatikgebäude)

Vorbesprechung am 15. April

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 1,5-stündigen Vortrag vorstellen. Eine Ausarbeitung muss nicht angefertigt werden.

Eine Übersicht findet sich auf den Einführungsfolien.

Aktuelles

15.04. – Falls Euch bei der Einarbeitung in Euer Thema Begriffe unterkommen, die bereits früher definiert wurden und die Ihr nicht versteht, so schaut mal in die Vorversion des Buchs oder wendet Euch an Euren jeweiligen Betreuer. Dieser kann Euch weiterhelfen. Außerdem: Neuer Link zu Complexity Zoo (siehe auch Linksammlung am Ende der Seite), Link zur Buchvorversion repariert (siehe Abschnitt „Themen“)
21.04. Die Folien von der Einführungsveranstaltung sind online.

Themen

Der Inhalt orientiert sich am Buch „Computational Complexity: A Modern Approach“ von Sanjeev Arora und Boaz Barak. Eine Vorversion des Buches ist im Netz frei verfügbar. Die endgültige Buchversion hat sich gegenüber dieser jedoch in einigen Bereichen stark verändert. In der Informatik-Bibliothek gibt es ein Präsenzexemplar.

TerminBetreuungThemaStudenten
06.05.FranziskaKurze Wiederholung der schon bekannten Dinge (Klassen P, NP, NP-Competeness, Reduktion usw.), die Klassen coNP, EXP und NEXP, weitere Gedankenexperimente „Was wäre wenn…?“, untere Schranken für die Länge von Resolutionsbeweisen als Hinweis auf NP ungleich coNPAdrian, Florian
13.05.TanjaDiagonalisierung als Beweistechnik (z.B. für die Existenz echter Time-Complexity-Hierarchien und die Existenz von nicht NP-vollständigen Sprachen in NP\P) sowie die Grenzen dieser Beweistechnik in Bezug auf die Frage P ungleich NP?, Vorstellung der polynomiellen HierarchieCorvin, Matthias
20.05.FabianSpace Complexity: Die Klasse PSPACE und ihr Verhältnis zu P und NP, Gemeinsamkeiten und Unterschiede zwischen Time- und Space ComplexityRaphael, Valentin
27.05ThomasBoolean Circuits: Ein alternatives Modell zur Turingmaschine, daraus resultierende Komplexitätsklassen und deren Verhältnis zu P und NP, Bedeutung des Modells für die Frage P ungleich NP?Matthias G., Saskia
03.06.IgnazCircuit lower bounds: Die Klassen AC0 und ACC0, Hastad's Switching Lemma und die Erkenntnis, dass es bereits einfache Funktionen ohne polynomielle Circuits gibt Souhail, Yassine
10.06.TobiasRandomisierung und Derandomisierung: Probabilistische Turingmaschinen, daraus resultierende Komplexitätsklassen, deren Zusammenhang mit Boolean Circuits und die Konzequenzen für die Frage P ungleich NP?Nicolai, Christian
17.06.MichaelInteraktive Beweise: Interagierende Beweiser und probabilistische Verifizierer, die Klassen IP und AM und die besondere Rolle des Graph-Isomorphie-ProblemsNicolas
24.06.IgnazDas PCP-Theorem und Approximation: Probabilistic Checkable Proofs und deren Bedeutung für die Suche nach guten ApproximationenOliver, Johannes
01.07.BenjaminKomplexität von Zählproblemen: Die Klasse #P, Zusammenhänge zwischen P, NP und #P und weiteren KlassenDennis, Stefan
08.07.MoritzEntscheidungsbäume: Ein einfacheres Modell als TMs, Verhalten der resultierenden Komplexitätsklassen, Yao's Min-Max-Lemma als Instrument zur Bestimmung unterer Komplexitätsschranken randomisierter AlgorithmenBenedict
15.07.RomanAverage Case Complexity: Die Klassen distP und distNP (analog zu P und NP) und der Satz von Levin zur Existenz eines distNP-vollständigen ProblemsAkin, Tobias

Literatur

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