Ein interaktives Beweissystem besteht aus zwei Agenten, der eine Beweiser, der andere Verifizierer genannt, die über einen festgelegten Kanal miteinander kommunizieren. Der Beweiser möchte den Verifizierer überzeugen, daß er selbst, der Beweiser, einen Beweis besitzt. In Form von wechselseitigen Fragen und Antworten, die über den Kommunikationskanal übertragen werden, versucht der Verifizierer, sich darüber klarzuwerden. Im einfachsten Fall gibt der Beweiser dem Verifizierer seinen Beweis, und der Verifizierer verifiziert, daß es sich dabei tatsächlich um einen Beweis handelt. Interessant wird es, wenn der Beweiser nicht Willens oder in der Lage ist, seinen Beweis vollständig oder teilweise zu übermitteln.

Interaktive Beweissysteme sind ein recht junges Berechnungsmodell. Durch verschiedene Einschränkungen an die beiden Agenten oder die Anzahl der zulässigen Frage-Antwort-Runden lassen sich Komplexitätsklassen definieren. Die Untersuchung dieser Komplexitätsklassen hat einige der interessantesten, spannendsten und weitreichendsten Ergebnisse der Informatik der letzten Jahre hervorgebracht, nämlich den ersten nichtrelativierbaren Beweis für die Gleichheit zweier Komplexitätsklassen (IP = PSPACE), das PCP-Theorem (PCP steht für probabilistically checkable proofs) und Zero-Knowledge-Beweise. Das PCP-Theorem liefert eine überraschende Aussage über NP und hat bedeutende Anwendungen im Bereich der (Nicht-)Approximierbarkeit; Zero-Knowledge-Beweise spielen eine große Rolle in der Kryptographie.

Vorlesungsinhalt

Wir werden interaktive Beweissysteme untersuchen und ihre Eigenschaften kennenlernen. Wir werden insbesondere die beiden wichtigen Aussagen, nämlich IP = PSPACE und das PCP-Theorem, kennenlernen und beweisen (soweit es sich innerhalb der Vorlesung einrichten läßt). Zur Unterhaltung werden zwischendurch ein paar Anwendungen vorgestellt.

Teilnahmevoraussetzungen

Die Vorlesung setzt im wesentlichen ein grundlegendes Verständnis von Turing-Maschinen und deren Arbeitsweise voraus. Weitergehende Grundkenntnisse aus der Komplexitätstheorie sind hilfreich, für den erfolgreichen Besuch der Vorlesung aber nicht notwendig.

Termine

Dozent

Daniel Meister