Titolo originale:
On Doubly-Efficient Interactive Proof Systems
Contenuto del libro:
Un sistema di prove interattivo è detto doppiamente efficiente se la strategia del prover prescritta può essere implementata in tempo polinomiale e la strategia del verificatore può essere implementata in tempo quasi lineare. Tali sistemi di prova rendono disponibili i vantaggi dei sistemi di prova interattivi agli agenti della vita reale che sono limitati al calcolo in tempo polinomiale.
On Doubly-Efficient Interactive Proof Systems esamina alcuni dei risultati noti relativi ai sistemi di prova interattivi doppiamente efficienti. Inizia presentando due semplici costruzioni per t-no-CLIQUE, dove la prima costruzione offre il vantaggio di essere generalizzata a qualsiasi insieme “localmente caratterizzabile” e la seconda costruzione offre il vantaggio di preservare il sapore combinatorio del problema. Si passa poi a due costruzioni più generali di sistemi di prova interattivi doppiamente efficienti: il sistema di prova per gli insiemi che hanno circuiti a profondità vincolata (uniforme) e il sistema di prova per gli insiemi che sono riconosciuti in tempo polinomiale e in uno spazio ridotto.
La presentazione della costruzione GKR è completa ed è leggermente diversa dalla presentazione originale. Viene fornita una breve panoramica della costruzione RRR.
Altre informazioni sul libro:
| ISBN: | 9781680834246 |
| Autore: | |
| Editore: | |
| Lingua: | inglese |
| Rilegatura: | Copertina morbida |
Acquisto:
Attualmente disponibile, in magazzino.
