Sobre sistemas de prueba interactivos doblemente eficientes

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.