Über doppelt-effiziente interaktive Beweissysteme

Über doppelt-effiziente interaktive Beweissysteme (Oded Goldreich)

Originaltitel:

On Doubly-Efficient Interactive Proof Systems

Inhalt des Buches:

Ein interaktives Beweissystem wird als doppelt effizient bezeichnet, wenn die vorgeschriebene Prover-Strategie in polynomialer Zeit und die Strategie des Verifiers in nahezu linearer Zeit implementiert werden kann. Solche Beweissysteme machen die Vorteile interaktiver Beweissysteme für reale Agenten verfügbar, die auf die Berechnung in Polynomialzeit beschränkt sind.

In On Doubly-Efficient Interactive Proof Systems werden einige der bekannten Ergebnisse zu doppelt effizienten interaktiven Beweissystemen zusammengefasst. Zunächst werden zwei einfache Konstruktionen für t-no-CLIQUE vorgestellt, wobei die erste Konstruktion den Vorteil bietet, dass sie auf jede „lokal charakterisierbare“ Menge verallgemeinert werden kann, und die zweite Konstruktion den Vorteil bietet, dass der kombinatorische Charakter des Problems erhalten bleibt. Anschließend werden zwei allgemeinere Konstruktionen von doppelt effizienten interaktiven Beweissystemen vorgestellt: das Beweissystem für Mengen, die (einheitliche) Schaltkreise mit begrenzter Tiefe haben, und das Beweissystem für Mengen, die in Polynomialzeit und auf kleinem Raum erkannt werden.

Die Darstellung der GKR-Konstruktion ist vollständig und unterscheidet sich etwas von der ursprünglichen Darstellung. Für die RRR-Konstruktion wird ein kurzer Überblick gegeben.

Weitere Daten des Buches:

ISBN:9781680834246
Autor:
Verlag:
Sprache:Englisch
Einband:Taschenbuch

Kauf:

Derzeit verfügbar, auf Lager.

Ich kaufe es!

Weitere Bücher des Autors:

Fundierte Grundlagen für die Kryptographie: Über die Arbeit von Shafi Goldwasser und Silvio Micali -...
Die Kryptographie befasst sich mit der...
Fundierte Grundlagen für die Kryptographie: Über die Arbeit von Shafi Goldwasser und Silvio Micali - Providing Sound Foundations for Cryptography: On the work of Shafi Goldwasser and Silvio Micali
Grundlagen der Kryptographie: Band 1, Grundlegende Werkzeuge - Foundations of Cryptography: Volume...
Die Kryptographie befasst sich mit der Konzeption,...
Grundlagen der Kryptographie: Band 1, Grundlegende Werkzeuge - Foundations of Cryptography: Volume 1, Basic Tools
Computerkomplexität - Computational Complexity
Dieses Buch bietet eine umfassende Perspektive auf moderne Themen der Komplexitätstheorie, die ein zentrales Gebiet der...
Computerkomplexität - Computational Complexity
Solide Grundlagen für die Kryptographie: Zu den Arbeiten von Shafi Goldwasser und Silvio Micali -...
Die Kryptographie befasst sich mit der...
Solide Grundlagen für die Kryptographie: Zu den Arbeiten von Shafi Goldwasser und Silvio Micali - Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali
Grundlagen der Kryptographie: Band 2, Grundlegende Anwendungen - Foundations of Cryptography: Volume...
Die Kryptografie befasst sich mit der Konzeption,...
Grundlagen der Kryptographie: Band 2, Grundlegende Anwendungen - Foundations of Cryptography: Volume 2, Basic Applications
Über doppelt-effiziente interaktive Beweissysteme - On Doubly-Efficient Interactive Proof...
Ein interaktives Beweissystem wird als doppelt effizient...
Über doppelt-effiziente interaktive Beweissysteme - On Doubly-Efficient Interactive Proof Systems
Einführung in die Eigenschaftsprüfung - Introduction to Property Testing
Die Eigenschaftsprüfung befasst sich mit der Entwicklung superschneller Algorithmen für...
Einführung in die Eigenschaftsprüfung - Introduction to Property Testing
P, Np, und Np-Vollständigkeit: Die Grundlagen der Computerkomplexität - P, Np, and Np-Completeness:...
Der Schwerpunkt dieses Buches liegt auf der...
P, Np, und Np-Vollständigkeit: Die Grundlagen der Computerkomplexität - P, Np, and Np-Completeness: The Basics of Computational Complexity

Die Werke des Autors wurden von folgenden Verlagen veröffentlicht:

© Book1 Group - Alle Rechte vorbehalten.
Der Inhalt dieser Seite darf weder teilweise noch vollständig ohne schriftliche Genehmigung des Eigentümers kopiert oder verwendet werden.
Letzte Änderung: 2024.11.13 22:11 (GMT)