In der Vorlesung werden die Grundlagen der Komplexitätstheorie erarbeitet. In einem ersten Abschnitt der Vorlesung werden die Grundbegriffe und -konzepte der Komplexitätstheorie behandelt, wie z.B. Komplexität von Problemen und Algorithmen, Berechnungsmodelle und Akzeptierungsmodi, Komplexitätsklassen (P, NP) und Reduktionskonzepte. Im zweiten Abschnitt der Vorlesung werden die Komplexitätsklassen P und NP und die zu ihrer Charakterisierung entwickelten Konzepte und Methoden im Detail besprochen. Neben der Charakterisierung NP-vollständiger Probleme werden dabei auch randomisierte und approximierte Berechnungen behandelt. Im dritten Abschnitt der Vorlesung geht es dann um Komplexitätsuntersuchungen und -klassen innerhalb von P (z.B. NC, L und NL) während im vierten Abschnitt wichtige Komplexitätsklassen über NP (z.B. Polynomialzeithierarchie, PSPACE, EXP) besprochen werden.

Beginn der Veranstaltungen zum WS03/04: 28.10.2003;
Vorlesung: Dienstag und Donnerstag 08-10 Uhr;
Übung: Mittwoch 08-10 Uhr.

Die Vorlesung wird sowohl live ins Internet übertragen als auch aufgezeichnet. Die Vorlesung kann ohne besondere Voreinstellungen mit dem kostenlosen RealPlayer an jedem z.B. über ISDN oder DSL mit dem Internet verbundenen Rechner verfolgt werden.
Zu jeder Vorlesung gibt es ein Übungsblatt, welches in der darauffolgenden Woche abzugeben ist.