On Doubly-Efficient Interactive Proof Systems
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.
| ISBN: | 9781680834246 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Taschenbuch |
Derzeit verfügbar, auf Lager.
