Komplexitätstheorie

i.d.R. unregelmäßig angeboten

• Mathematische Beweise verstehen können und in der Lage sein, einfache Beweise selbst zu führen.

• Kenntnis der wichtigsten Komplexitätsklassen und ihrer Zusammenhänge erworben haben.

• Den kombinatorischen Charakter von NP-vollständigen Problemen verstehen und die Berechnungskomplexität von typischen Informatik-Problemen grob einschätzen können.

• Das Werkzeug der Reduktion kennen und in Beispielen anwenden könenn.

• Einblick haben in die Grenzen der effizienten Berechenbarkeit und in die Schwierigkeiten der Komplexitätstheorie.

Die Komplexitätstheorie beschäftigt sich mit den Grenzen der Berechenbarkeit unter beschränkten Ressourcen: welche Probleme lassen sich mit einem bestimmten Aufwand an Zeit (oder anderen Ressourcen) lösen, welche nicht? Sie stellt damit eine wichtige Grundlage für den Entwurf und das Verständnis von effizienten Algorithmen dar und versucht darüberhinaus, die natürliche Neugier nach dem in der Informatik prinzipiell machbaren zu befriedigen. Die Vorlesung beschäftigt sich mit folgenden Themen:

• Grundlegende Begriffe wie Reduktionen, Härte und Vollständigkeit
• Das P vs. NP Problem und dessen Variationen
• NP-vollständige Probleme aus verschiedenen Teilgebieten der Informatik
• Hierarchietheoreme und verwandte Resultate
• Platzkomplexitätsklassen wie PSpace und LogSpace
• Schaltkreiskomplexität und effiziente Parallelisierbarkeit
• Die polynomielle Hierarchie

• Oded Goldreich. Computational Complexity: a Conceptual Perspective. Cambridge University Press, 2008.
• Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
• Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• Ingo Wegener. Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. Springer, 2003.
• Michael Sipser. Introduction to the Theory of Computation (2nd Edition). Thomson Course Technology, 2006