Seminar: Interaktive Beweise

Dozenten: Prof. Johannes Köbler und Olaf Beyersdorff

Termin:	`SE Di 15-17 (RUD 25, IV.109) J. Köbler / O. Beyersdorff`

Zuordnung:	Hauptstudium, Seminar

Inhalte und Lernziele

Die Klasse NP enthält alle Sprachen, für die sich die Wortzugehörigkeit durch einen effizient verifizierbaren Beweis zeigen lässt. In einem Schüler-Lehrer-Modell entspricht dies der Situation, dass der (allwissende) Lehrer den (durch Polynomialzeit beschränkten) Schüler durch Vorlage des Beweises überzeugen kann. Dieses Modell kann dadurch erweitert werden, dass der Schüler an Schlüsselstellen des Beweises (unvorhersehbare) Fragen stellen darf. Überraschenderweise existieren solche "interaktiven Beweise" für alle Sprachen in PSPACE (im Falle von zwei Lehrern sogar für alle Sprachen in NEXP).

Themen

16.4. und 23.4.	Themenvorstellung und Einführung		Johannes Köbler
30.4. und 7.5.	IP=PSPACE	(Köbler)	Daniel Rolf
14.5. und 21.5.	Arthur-Merlin Spiele (Teil 1, Teil 2)	(Beyersdorff)	Lars Siggelkow, Ralf Berger
28.5. und 4.6.	Multi-Prover Beweissysteme (Teil 1, Teil 2)	(Köbler)	Ben Bäßler, Valentin Ziegler
11.6. und 18.6.	Zero-Knowledge Protokolle (Teil1, Teil 2)	(Beyersdorff)	Björn Karge, Jens Harzer
25.6.	Probabilistically Checkable Proofs und Approximationsalgorithmen	(Köbler)	Doratha Drake

B. Bäßler