Prueba interactiva para HORN-SAT?

10

¿Hay alguna manera de que un probador pueda convencer a un verificador de que alguna expresión de HORN-SAT es satisfactoria?

Por supuesto, esto puede parecer una tontería, ya que existen algoritmos de tiempo lineal para HORN-SAT. Por otro lado, HORN-SAT es P-completo, lo que significa que no tiene algoritmos de espacio logarítmico a menos que P = L. En consecuencia, restrinja las capacidades computacionales del verificador a L. Ahora el verificador es muy débil, por lo que el problema ya no es tonto.

Otro giro en esto es si puede ser una prueba de conocimiento cero.

cc.complexity-theory interactive-proofs zero-knowledge Shaun Harker
fuente
1
En el caso de conocimiento distinto de cero, creo que la verificación ingenua utilizando una asignación de verdad satisfactoria como certificado solo requiere espacio de registro, siempre que la entrada y el certificado estén escritos en cintas de solo lectura que no cuentan como espacio.
Tsuyoshi Ito
@ Tsuyoshi: No veo cómo hacer una verificación ingenua solo en el espacio de registro. Si pudiéramos, ¿no mostraría eso que HORN-SAT está en NL y, por lo tanto, por P-completitud daría P = NL?
Shaun Harker
No. Supuse que el certificado está en una cinta de solo lectura, que es diferente de la verificación realizada por NL.
Tsuyoshi Ito
@ Tsuyoshi: Ah, entonces puedes leer el certificado muchas veces, mientras que una definición de NL basada en un certificado tendría un certificado que solo se puede leer una vez.
Shaun Harker

Respuestas:

11

Esta http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf encuesta realizada por Anne Condon contiene muchos datos sobre sistemas de prueba interactivos limitados por el espacio.

Existen varios modelos, y las principales diferencias son si permite monedas privadas para el verificador (IP) o solo monedas públicas (AM), y si también restringe el tiempo de verificación a polinomio (no implica el espacio limitado solo).

Sin la restricción de tiempo, la respuesta es sí: IP (espacio de registro) contiene EXP y AM (espacio de registro) = P.

Tenga en cuenta que la IP (espacio de registro) es más probable que la IP estándar. Por otro lado, IP (log-space, poly-time) = IP = PSPACE.

AM (log-space, poly-time) = P debido a 'Delegación de computación: pruebas interactivas para muggles' por Goldwasser et al., STOC 2008.

Además, el documento 'Cero conocimiento con verificadores de espacio logarítmico' de Kilian (FOCS 88) muestra cómo obtener un sistema de prueba de conocimiento poli-tiempo cero de espacio logarítmico para todo en IP (obviamente con monedas privadas).

Hartmut Klauck
fuente
1
También encontré un artículo titulado Delegar computación: pruebas interactivas para muggles . ¿El teorema 3 de este trabajo muestra que AM (log-space, poly-time) = P?
Shaun Harker
¡Sí, de hecho lo demuestran!
Hartmut Klauck