Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Inhalte und Lernziele

In diesem Seminar werden aktuelle Themen der Theoretischen Informatik, insbesondere der Komplexitätstheorie und der Kryptologie behandelt. Hierbei gehen wir auch gern auf Teilnehmerwünsche ein. In diesem Semester liegt der Schwerpunkt auf dem PCP-Theorem und Approximationsalgorithmen.
PCP steht für probabilistically checkable proofs: Das sind Beweise, die man nicht vollständig lesen muss, um ihre Richtigkeit zu überprüfen - stattdessen genügt das Betrachten weniger, zufällig ausgewählter Bits, um gültige und ungültige Beweise mit hoher Wahrscheinlichkeit zu unterscheiden. Das PCP-Theorem besagt, dass für jede Sprache in NP (für die also Beweise existieren, die in polynomieller Zeit geprüft werden können) auch PCPs existieren.
Approximationsalgorithmen kommen zum Einsatz, wenn die exakte Lösung eines Optimierungsproblems nicht effizient möglich ist. Dies betrifft beispielsweise Max-3-SAT, wo für eine in 3-KNF gegebene Formel nach der maximalen Anzahl gleichzeitig erfüllbarer Klauseln gefragt wird. Einerseits sind für viele praktisch relevante Optimierungsprobleme gute Approximationsalgorithmen bekannt, andererseits lassen sich in vielen Fällen mithilfe des PCP-Theorems Grenzen der Approximierbarkeit zeigen.
Vorkenntnisse aus der Komplexitätstheorie sind zum Besuch dieses Seminars nützlich, jedoch nicht notwendig.

Seminarankündigung (PDF)

Vorträge

Daten in Klammern haben vorläufigen Charakter.

• Einführung und Themenvergabe
  18.10.2011
• Jennifer Gehrke
  Approximation von Optimierungsproblemen
  (8.11. und 15.11.2011)
• Fabian Weber
  PCP und Nichtapproximierbarkeit
  (29.11. und 6.12.2011)
• Erik Ludwig
  Das PCP-Theorem (Teil 1)
  03.01., 10.01., und 17.01.2012
• Immanuel Sims
  Das PCP-Theorem (Teil 2)
  24.01. und 31.01.2012