Komplexitätstheorie, mit Anwendungen in der Kryptographie

Was ist ein "effizienter" Algorithmus? Kann jede algorithmische Aufgabe effizient gelöst werden? Oder gibt es inhärent schwierige Probleme? Die Komplexitätstheorie stellt eine streng mathematische Grundlage für die Diskussion dieser Fragen bereit. In dieser Vorlesung behandelte Themen sind

• Maschinenmodell, Laufzeit- und Speicherkomplexität, Separationen,
• Nichtdeterminismus, Reduktionen, Vollständigkeit,
• die polynomiale Hierarchie,
• Probabilismus, Einwegfunktionen,
• Alternierung, interaktive Beweise, Zero-Knowledge.

Diese Themen werden mit praktischen Beispielen illustriert. Die Vorlesung gibt einen Ausblick auf Anwendungen der Komplexitätstheorie, insbesondere auf dem Gebiet der Kryptographie.

Prüfbarkeit

Die Vorlesung ist prüfbar im Master- (5 LP im Modul "Fortgeschrittene Themen der Kryptographie") und im Diplomstudiengang (3 SWS im Vertiefungsfach "Kryptographie und Sicherheit").

Vorlesungstermine

Die Vorlesung findet jeweils dienstags (09.45, SR236) und 14-täglich donnerstags (09.45, SR236) statt.

Behandelte Themen

• 12.04.2011: Überblick, Maschinenmodell, Universalität des Maschinenmodells
• 14.04.2011: Elementare Komplexitätsklassen, Gödelnumerierung, universelle TM, nicht berechenbare Probleme
• 19.04.2011: Inklusionen von Komplexitätsklassen, deterministische Zeithierarchie
• 26.04.2011: Nichtdeterministische Zeithierarchie, Satz von Savitch (PSPACE=NPSPACE)
• 28.04.2011: Alternative Definition von NP, Reduktionen, Satz von Cook-Levin, Satz von Ladner
• 03.05.2011: Satz von Baker, Gill, Solovay (Schwierigkeit P=NP-Beweis), PKE-Schema
• 10.05.2011: Satz von Brassard (Schwierigkeit, ein PKE-Schema auf NP-Härte zu beweisen), Polly Cracker
• 12.05.2011: Alternierung, polynomielle Hierarchie
• 17.05.2011: AP=PSPACE, deterministische interaktive Beweissysteme
• 24.05.2011: Interaktive Beweissysteme, PSPACE enthält IP (Anfang)
• 26.05.2011: PSPACE enthält IP (Ende), Arithmetisierung einer Formel
• 31.05.2011: IP enthält PSPACE (Anfang)
• 07.06.2011: IP enthält PSPACE (Ende)
• 09.06.2011: Schaltkreise, Grenzen der Mächtigkeit von Schaltkreisen
• 14.06.2011: Mehr zu Schaltkreisen, NCi, ACi
• 21.06.2011: Switching-Lemma, PARITY ist nicht von AC0-Schaltkreisen berechenbar
• 28.06.2011: Randomisierte Algorithmen, BPP, RP, Polynomial Identity Testing
• 05.07.2011: Derandomisierung, PRGs, Erweiterung von PRGs
• 07.07.2011: Konstruktion von PRGs, Goldreich-Levin-Konstruktion
• 12.07.2011: Probabilistically Checkable Proofs

Literatur

Die Vorlesung folgt dem Buch "Computational Complexity: A Modern Approach" von Arora und Barak. Eine Vorabversion des Buchs ist online verfügbar unter http://www.cs.princeton.edu/theory/complexity/

Skript

Ein Vorlesungsskript ist hier verfügbar. (Das Skript wird jedoch im Lauf der Vorlesung angepaßt und erweitert werden.)