Randomisierte und interaktive Berechnung

Algorithmen, die Münzen werfen oder einen Dialog mit einem mächtigen, aber nicht vertrauenswürdigen Prüfer führen können, führen zu Komplexitätsklassen wie BPP und IP, die unser Verständnis dessen, was effiziente Verifikation erreichen kann, neu gestalten.

Definition

Randomisierte Berechnung erweitert eine Maschine um den Zugriff auf Zufallsbits und misst die Wahrscheinlichkeit einer korrekten Antwort, während interaktive Berechnung einem Verifizierer mit polynomialer Zeit erlaubt, Nachrichten mit einem Prüfer auszutauschen; die resultierenden Klassen erfassen Probleme, die mit begrenztem Fehler lösbar oder durch Interaktion verifizierbar sind.

Scope

Dieses Thema behandelt probabilistische Komplexitätsklassen einschließlich BPP, RP und ZPP und die Frage, ob Zufälligkeit eliminiert werden kann, interaktive Beweissysteme und das Theorem, das IP mit PSPACE identifiziert, Zero-Knowledge-Beweise und probabilistisch überprüfbare Beweise, die der Härte der Approximation zugrunde liegen.

Core questions

• Ermöglicht der Zugriff auf Zufälligkeit Algorithmen, mehr Probleme effizient zu lösen?
• Kann ein begrenzter Verifizierer Behauptungen eines nicht vertrauenswürdigen, mächtigen Prüfers überprüfen?
• Wie kann man von der Wahrheit einer Aussage überzeugt werden, ohne etwas anderes zu erfahren?
• Wie schränkt die interaktive und probabilistische Beweisprüfung die Approximation ein?

Key theories

IP gleich PSPACE

Die Sprachen, die durch ein interaktives Protokoll zwischen einem Verifizierer mit polynomialer Zeit und einem allmächtigen Prüfer beweisbar sind, sind genau diejenigen, die in polynomialem Raum entscheidbar sind, ein bemerkenswertes Maß für die Macht der Interaktion.

Das PCP-Theorem

Jedes Problem in NP besitzt Beweise, die durch das Lesen einer konstanten Anzahl zufällig ausgewählter Bits verifiziert werden können, ein Ergebnis, das die präzise Schwelle festlegt, jenseits derer die Approximation vieler Optimierungsprobleme NP-schwer ist.

Clinical relevance

Diese Ideen haben direkte technologische Auswirkungen: Zero-Knowledge-Beweise ermöglichen Authentifizierungs- und datenschutzfreundliche Protokolle und untermauern die überprüfbare Berechnung in Blockchains, während probabilistisch überprüfbare Beweise erklären, warum viele Optimierungsprobleme nicht effizient approximiert werden können, und somit leiten, wo Approximationsalgorithmen erfolgreich sein können und wo nicht.

History

Interaktive und Zero-Knowledge-Beweise wurden Mitte der 1980er Jahre von Goldwasser, Micali und Rackoff sowie von Babai eingeführt. Shamir bewies 1990, dass IP gleich PSPACE ist, und das PCP-Theorem, das Anfang der 1990er Jahre von Arora und anderen vervollständigt wurde, revolutionierte die Untersuchung der Approximation, während die bestehende Vermutung, dass randomisierte polynomiale Zeit gleich deterministischer polynomialer Zeit ist, weiterhin offen bleibt.

Debates

Fügt Zufälligkeit echte Rechenleistung hinzu?

Viele Ergebnisse deuten darauf hin, dass BPP unter plausiblen Härteannahmen gleich P ist, was bedeutet, dass Zufälligkeit prinzipiell aus effizienten Algorithmen entfernt werden könnte. Ob diese Derandomisierung bedingungslos gilt, ist ungelöst und lässt offen, wie wesentlich Zufälligkeit wirklich ist.

Key figures

• Shafi Goldwasser
• Silvio Micali
• László Babai
• Adi Shamir

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

Wie kann das Werfen von Münzen einem Algorithmus helfen?

Zufälligkeit ermöglicht es einem Algorithmus, Worst-Case-Eingaben zu vermeiden, indem er Entscheidungen trifft, die der Gegner nicht vorhersagen kann, was oft zu einfacheren oder schnelleren Verfahren führt, wie bei der Primzahlprüfung. Die Fehlerklasse BPP erfasst Probleme, die auf diese Weise mit einer geringen, kontrollierbaren Fehlerwahrscheinlichkeit lösbar sind.

Was ist ein Zero-Knowledge-Beweis?

Es ist ein interaktives Protokoll, das einen Verifizierer davon überzeugt, dass eine Aussage wahr ist, ohne etwas anderes als ihre Wahrheit preiszugeben, nicht einmal, warum sie gilt. Solche Beweise ermöglichen es beispielsweise, zu beweisen, dass man ein Passwort oder Geheimnis kennt, ohne es offenzulegen, und sie sind grundlegend für die moderne kryptographische Privatsphäre.