Übung Übungen zur Komplexitätstheorie

Viele Konzepte der strukturellen Komplexitaetstheorie stammen urspruenglich aus der Rekursionstheorie. Dort befasste man sich mit der Frage, welche Probleme ueberhaupt algorithmisch loesbar sind. Ausserdem bemuehte man sich, die unloesbaren Probleme zu klassifizieren. In der Komplexitaetstheorie fragt man nun danach, welche Probleme mit vertretbarem Aufwand geloest werden koennen. Dabei hat sich inzwischen die Uebereinstimmung ergeben, dass ein Problem mit vertretbarem Auswand geloest werden kann, wenn es in polynomialer Rechenzeit geloest werden kann. Dies fuehrte zur Klasse P. Man bemuehte sich nun, die Probleme zu klassifizieren, die nicht in P zu liegen scheinen. Bei diesen Untersuchungen hat man viele Konzepte aus der Rekursionstheorie auf den subrekursiven Bereich uebertragen. Die dabei aufgetretenen Fragen und Probleme zaehlen vielfach zu den bedeutensten der (theoretischen) Informatik. Sie beruehren unmittelbar unser Verstaendnis von dem, was algorithmisch mit vertretbarem Aufwand geloest werden kann. Die Vorlesung ist wie folgt aufgebaut: * Kapitel 1: Turing Maschinen Das benutzte Rechnermodell wird vorgestellt. * Kapitel 2: Rechenzeit- und Speicherplatzbedarf als Komplexitaetsmasse Einige grundlegende Saetze ueber Zeit- und Platzklassen. * Kapitel 3: Untere Schranken fuer einige spezielle Sprachen * Kapitel 4: Einige zentrale Komplexitaetsklassen Einige spezielle Komplexitaetsklassen werden eingefuehrt, darunter die Klassen P, NP und PSPACE. Die Polynomialzeit-Reduzierbarkeit und die Vollstaendigkeit bzgl. dieser Reduzierbarkeit werden betrachtet. * Kapitel 5: Zeit-beschraenkte Turing-Reduzierbarkeiten * Kapitel 6: Nicht uniforme Komplexitaet Ein Komplexitaetsmass fuer endliche Mengen: die Groesse des Algorithmus, der eine solche endliche Menge akzeptiert. * Kapitel 7: Probabilistische Klassen * Kapitel 8: Chomsky Sprachen und ihre Komplexitaet J.L. Balcazar, J. Diaz, J. Gabborro: Structural Complexity, I und II EATCS Monographs on Theoretical Computer Science, Vol. 11 und 22, Springer, 1988. Ergaenzende Literatur: - M.R. Garey, D.S. Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness Freeman, San Francisco, 1979. - J.E. Hopcraft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation Addison-Wesley, 1979. - K.R. Reischuk: Komplexitaetstheorie, Band I: Grundlagen Teubner, Stuttgart, 1999. - H. Vollmer: Introduction to Circuit Complexity Springer, Berlin, 1999. VoraussetzungenTheoretische Informatik I oder entsprechende Kenntnisse Leistungsnachweismuendliche Pruefung FB 17 Mathematik Uni Kassel SS2007 Informatik FB 17 Mathematik Professor Otto Friedrich Professor