Vorlesung Komplexitätstheorie

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. Im ersten Teil stehen klassische Resultate im Vordergrund: z.B. die Korrespondenz zwischen Spielen und Speicherplatz-Beschränkungen, der Nachweis, dass sich mit mehr Platz oder Zeit auch mehr Probleme lösen lassen, weitere grundlegende Beziehungen zwischen Zeit- und Platzbasierten Klassen, und die Komplexitätswelt zwischen NP und PSPACE. Weiterhin wird die Komplexitätstheorie paralleler, zufallsbasierter und approximativer Algorithmen in Grundzügen vorgestellt. Der zweite Teil der Vorlesung beschäftigt sich dann mit etwas neueren Themen: Komplexitätstheorie des interaktiven Rechnens, des probabilistische Beweisens und der Kryptographie. Weitere Themen sind parametrisierte Komplexitätstheorie und untere Schranken für Schaltkreiskomplexität. Die Vorlesung folgt nicht einem einzelnen Buch. Die folgende Literatur ist zu empfehlen. • Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003. • Arora, Barak. 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. Bemerkung Die Veranstaltung richtet sich an Student(inn)en der Master-Studiengänge in Informatik und Angewandter Informatik und zugleich an Student(inn)en im Hauptstudium der Diplomstudiengänge, dort mit dem Namen -Komplexitätstheorie und effiziente Algorithmen- und der Veranstaltungsnummer 042823. Zur genauen Einbettung in die Masterstudiengänge liefert das entsprechende Modulhandbuch weitere Informationen: http://www.cs.uni-dortmund.de/nps/de/Studium/Studieng__nge/Master-Studiengang_Informatik/Modulhandbuch_Master_Informatik/Modulhandbuch_gesamt/Master_20070806.pdf. Es gibt zu dieser Vorlesung einen EWS-Arbeitsraum. Dort werden die Übungsblätter bereitgestellt und es ist die Nutzung der Forums- und Mail-Funktionen vorgesehen. Anmeldung: https://ews.tu-dortmund.de/ngGui/signon/lsf-83118 Technische Universität Dortmund SoSe 2013 Informatik Prof. Dr. Schwentick Thomas