Título original:
On Doubly-Efficient Interactive Proof Systems
Contenido del libro:
Un sistema de pruebas interactivo se denomina doblemente eficiente si la estrategia prescrita del prover puede implementarse en tiempo polinómico y la estrategia del verificador puede implementarse en tiempo casi lineal. Estos sistemas de prueba ponen las ventajas de los sistemas de prueba interactivos a disposición de los agentes de la vida real que están restringidos al cálculo en tiempo polinómico.
En On Doubly-Efficient Interactive Proof Systems se analizan algunos de los resultados conocidos sobre los sistemas de prueba interactivos doblemente eficientes. Comienza presentando dos construcciones simples para t-no-CLIQUE, donde la primera construcción ofrece la ventaja de ser generalizada a cualquier conjunto «localmente caracterizable», y la segunda construcción ofrece la ventaja de preservar el sabor combinatorio del problema. A continuación, se pasa a dos construcciones más generales de sistema de prueba interactivo doblemente eficiente: el sistema de prueba para conjuntos que tienen circuitos (uniformes) de profundidad acotada y el sistema de prueba para conjuntos que se reconocen en tiempo polinomial y espacio pequeño.
La presentación de la construcción GKR es completa y algo diferente de la presentación original. Se ofrece una breve visión general de la construcción RRR.
Otros datos del libro:
| ISBN: | 9781680834246 |
| Autor: | |
| Editorial: | |
| Idioma: | inglés |
| Encuadernación: | Tapa blanda |
Compra:
Actualmente disponible, en stock.
