Komplexitätstheorie

• Am Donnerstag, 20.1., findet nachmittags im Hörsaal E 23 die feierliche Eröffnung des neuen Sonderforschungsbereiches 876 statt. Insbesondere gibt es von 14:30 Uhr bis 15:30 Uhr einen Vortrag von Johannes Gehrke, Cornell University, über Algorithmen für Datenströme. Aus diesem Anlass fällt die Komplexitätstheorie aus, die Vorlesungsteilnehmer werden aber ermutigt, sich den genannten Vortrag anzuhören.

Hier finden Sie aktuelle Informationen zum Verlauf der Vorlesung

Die Übungsblätter sind nicht mehr öffentlich.

1. Montag, 16-18 Uhr, OH14, E02
2. Mittwoch, 14-16 Uhr, OH 14, 104

Während bei der Untersuchung effizienter Algorithmen, die Untersuchung und Weiterentwicklung einzelner Algorithmen im Vordergrund steht, beschäftigt sich die Komplexitätstheorie mit der Klassifikation von Berechnungsproblemen nach ihrer algorithmischen Schwierigkeit. Sie versucht dabei, den inhärenten Ressourcenverbrauch zu bestimmen, z.B. hinsichtlich Rechenzeit oder Speicherplatz. Probleme mit gleichartigem Ressourcenverbrauch werden zu Komplexitätsklassen zusammengefasst. Die bekanntesten Komplexitätsklassen sind sicherlich P und NP, die die in polynomieller Zeit lösbaren bzw. verifizierbaren Probleme umfassen. Die Frage ob P und NP verschieden sind, wird als eine der bedeutendsten offenen Fragen der theoretischen Informatik, ja sogar der Mathematik, angesehen.

P und NP sind jedoch nur zwei Beispiele von Komplexitätsklassen. Andere Klassen ergeben sich unter anderem bei der Untersuchung der effizienten Parallelisierbarkeit von Problemen, der Lösbarkeit durch zufallsgesteuerte Algorithmen, und der approximativen Lösbarkeit von Problemen. Die Vorlesung hat das Ziel, einen breiten Überblick über die grundlegenden Konzepte und Resultate der Komplexitätstheorie zu geben.

• Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003.
• Arora. Computational Complexity: A Modern Approach. Cambridge University Press. Eine Vorabversion ist (immer noch) verfügbar unter: http://www.cs.princeton.edu/theory/index.php/Compbook/Draft
• Papadimitriou. Computational Complexity. Addison-Wesley. Reading. 1995.
• Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice Hall. New York. 1994.