zum Inhalt springen

Seminar über Komplexitätstheorie

Anhand einzelner Textbuchkapitel und Originalarbeiten sollen Inhalte der Komplexitaetstheorie vertieft und weiterführende Fragestellungen behandelt werden. Dabei sollen insbesondere auch Themen der Parametrisierten Komplexitätstheorie sowie Verbindungen zur Mathematischen Logik bearbeitet werden. 

(Einige) mögliche Themen sind:

  • Polynomiale Hierarchie
  • vollst. Erfüllbarkeitsprobleme struktureller und parameterisierter Komplexitätsklassen
  • Graphisomorphieproblem
  • QBF-SAT und PSPACE-Vollständigkeit
  • Algorithmik/Komplexität des KNF-SAT Problems
  • Primzahltest und Faktorisierung
  • Einführung in die Algebraische Komplexitaetstheorie
  • Blum-Shub-Smale-Modell

Voraussetzung sinnvoll (nicht zwingend): Teilnahme an der Vorlesung Theoretische Informatik.

Leistungsnachweis: Durch Ausarbeitung eines Referats samt Vortrag von ca. 60 min Länge

Termine: Vorbesprechung am 8. August 2008, 11.00 - 12.00 Uhr, Pohligstr. 1, Raum 616. In diesem Rahmen werden auch die Themen vergeben.

Literatur:

  • Papadimitriou, C. H.: Computational Complexity. Addison-Wesley, 1994.
  • Balcazar, J. L.; Diaz, J.; Gabarro, J.: Structural Complexity I, II. Springer, 1998.
  • Downey, R. G.; Fellows, M.R.: Parameterized Complexity. Springer, 1999.
  • Flum, J.; Grohe, M.: Parameterized Complexity Theory. Springer, 2006.
  • Schoening, U.: Algorithmik. Spektrum-Verlag, 2001.
  • Koebler, J.; Schoening, U.; Toran, J.: The graph isomorphism problem: its structural complexity. Birkhaeuser, 1993.
  • Buergisser, P.: Completeness and Reduction in Algebraic complexity theory. Springer-Verlag, 2000.
  • Buergisser, P.; Clausen, M.; Shokrollahi, M.A.: Algebraic complexity theory. Springer-Verlag, 1997.
  • Blum, Shub, Tucker, Smale: Computing over the reals. 1999.