Paralleles-Repetition-Theorem

Stell dir zwei Verdächtige vor, die in getrennten Räumen befragt werden. Vorher durften sie sich absprechen, während der Befragung aber nicht mehr. Ein Prüfer stellt jedem eine Frage und vergleicht die beiden Antworten. Passen sie zusammen, gilt die Aussage als bestätigt. Solche Befragungen nennt man in der Mathematik ein Spiel, und wenn die Verdächtigen lügen, haben sie trotzdem eine gewisse Chance, damit durchzukommen. Das Paralleles-Repetition-Theorem beantwortet die Frage: Wie klein wird diese Chance, wenn der Prüfer nicht eine Frage stellt, sondern hundert Fragen auf einmal, und alle hundert Antwortpaare zusammenpassen müssen?

Warum Lügner nicht einfach hundertmal Glück brauchen

Die naive Erwartung ist einfach. Wenn eine einzelne Runde mit 50 Prozent Wahrscheinlichkeit gelingt, sollten hundert Runden mit 0,5 hoch hundert gelingen. Das wäre eine unvorstellbar kleine Zahl. Diese Rechnung stimmt aber nur, wenn die Runden voneinander unabhängig sind.

Genau das sind sie nicht. Beide Befragten sehen alle hundert Fragen gleichzeitig, bevor sie antworten. Sie können ihre Antworten also miteinander verknüpfen. Zum Beispiel könnten sie so tricksen: Person A richtet ihre Antwort auf Frage 7 nach dem aus, was sie in Frage 3 gelesen hat. Damit erzeugen sie Korrelationen zwischen den Runden, die es einzeln nicht gab. Es gibt tatsächlich Spiele, bei denen dieser Trick funktioniert und die Betrugschance langsamer sinkt als naiv erwartet.

Der Satz ist deshalb ein echtes Ergebnis und keine Selbstverständlichkeit. Er wurde 1995 von Ran Raz bewiesen, nachdem die Frage jahrelang offen war. Sein Resultat: Die Betrugschance sinkt trotz aller Tricks exponentiell mit der Zahl der Runden. Der Abfall ist nur langsamer als in der naiven Rechnung, und wie viel langsamer, hängt davon ab, wie viele verschiedene Antworten überhaupt erlaubt sind.

Der Aufbau der Beweisidee

Ein Spiel dieser Art hat immer denselben Aufbau. Der Prüfer wählt zufällig ein Fragenpaar aus einer festen Liste. Eine Frage geht an den ersten Teilnehmer, die andere an den zweiten. Am Ende prüft eine feste Regel, ob die beiden Antworten zueinander passen. Die höchste Gewinnchance, die Lügner in einer Runde erreichen können, heißt der Wert des Spiels.

Bei der parallelen Wiederholung wird dieses Spiel n-mal gleichzeitig gespielt. Gewonnen ist nur, wenn alle n Runden gleichzeitig bestehen. Der Beweis zeigt nun: Der Wert dieses großen Spiels ist höchstens der ursprüngliche Wert, potenziert mit einem Bruchteil von n. Statt der naiven Rechnung mit dem vollen n steht dort also n geteilt durch einen Faktor, der von der Zahl der möglichen Antworten abhängt.

Die Idee dahinter lässt sich grob so beschreiben. Man nimmt an, die Lügner gewinnen alle n Runden mit relativ hoher Wahrscheinlichkeit. Dann zeigt man, dass es unter dieser Annahme mindestens eine Runde geben muss, die sich fast wie ein eigenständiges Einzelspiel verhält. Aus dieser einen Runde gewinnt man eine Strategie für das ursprüngliche Spiel, die besser ist als erlaubt. Das ist ein Widerspruch, also war die Annahme falsch. Solche Argumente arbeiten mit Informationsmaßen, die messen, wie viel die Runden voneinander verraten.

Bedeutung für Beweise, Sicherheit und Grenzen der Berechenbarkeit

Das Theorem ist ein Standardwerkzeug in der Komplexitätstheorie, dem Teilgebiet, das den nötigen Rechenaufwand von Problemen untersucht. Man braucht es überall dort, wo Prüfverfahren verlässlicher gemacht werden sollen, ohne sie länger als nötig zu machen. Es steckt in Beweisen darüber, wie gut sich bestimmte Optimierungsprobleme überhaupt näherungsweise lösen lassen.

In der Kryptografie taucht dasselbe Muster auf. Bei einem Nachweis ohne Preisgabe von Wissen überzeugt jemand sein Gegenüber, ein Geheimnis zu kennen, ohne es zu verraten. Solche Verfahren bestehen aus vielen kleinen Prüfrunden. Ob man diese Runden hintereinander oder gleichzeitig ablaufen lässt, macht einen Unterschied für die Sicherheit. Gleichzeitig ist schneller, aber nur der Satz garantiert, dass die Restschwäche dabei klein bleibt.

In Fachnachrichten liest man den Begriff heute vor allem im Zusammenhang mit Blockchain-Technik und Quantenphysik. Bei kryptografischen Beweissystemen, die Transaktionen verifizieren, geht es um genau diese Frage der Rundenzahl. In der Quanteninformation untersucht man Varianten, in denen die getrennten Teilnehmer verschränkte Teilchen teilen. Ob und wie stark der Satz dort noch gilt, ist ein aktives Forschungsgebiet.