Pruebas interactivas para coNP

9

Estoy tratando de entender los sistemas de prueba interactivos y probé el siguiente problema como ejercicio. Sabemos que e , entonces, ¿ tenemos sistemas de prueba interactivos (fáciles de entender) para ? $PH \subseteq PSPACE$ $IP=PSPACE$ $PH$

Un sistema interactivo para la prueba es trivial, pero no pudo conseguir un sistema de prueba interactiva incluso para . ¿Conoces un sistema de prueba interactivo explícito (quiero decir explícito sin pasar por la ruta ) para ? $NP$ $coNP$ $IP=PSPACE$ $coNP$

complexity-theory interactive-proof-systems Shitikanth
fuente

¿Podría aclarar qué quiere decir con sistema de prueba interactivo? Para aquellos que no están familiarizados con el término.

jmite

3

Incluso la inclusión

requiere técnicas no relativizadoras; La única forma conocida de mostrarlo es a través de la algebrización, como en la respuesta de Yuval. Mostrar

es simplemente una ligera modificación técnica de esta prueba.

c o N P \subseteq I P

$coNP \subseteq IP$

I P = P S P A C E

$IP=PSPACE$

sdcvvc

2

@sdcvvc, creo que su comentario merece ser publicado como respuesta. Explica por qué no hay ejemplos tan simples como los de NP.

Kaveh

6

Wikipedia describe ese ejemplo. Considere el problema UNNAT completo de coNP: dado un CNF en variables, queremos convencer al verificador de que no es satisfactoria. Aritmetizamos a un polinomio y elegimos algunos primos grandes . Sea $\varphi$ $n$ $\varphi$ $\varphi$ $p$ $q$ El protocolo procede de la siguiente manera:

p (x_{1}, \dots, x_{k}) = \sum_{x_{k + 1} = 0}^{1} \dots \sum_{x_{n} = 0}^{1} p (x_{1}, \dots, x_{n}) .

$p(x_1,\ldots,x_k) = \sum_{x_{k+1}=0}^1 \cdots \sum_{x_n=0}^1 p(x_1,\ldots,x_n).$

Prover envía al verificador un primo , y este último verifica que sea primo. $q \in (2^n,2^{n+1})$ $q$
Prover envía el verificador . El verificador verifica que , y envía al probador un aleatorio . $p(z) \in \mathbb{Z}_q[z]$ $p(0) + p(1) = 0$ $r_1$
Prover envía el verificador . El verificador verifica que , y envía al probador un aleatorio . $p(r_1,z) \in \mathbb{Z}_q[z]$ $p(r_1,0) + p(r_1,1) = p(r_1)$ $r_2$
Finalmente, el verificador obtiene , y verifica que tiene el valor correcto evaluando directamente. $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$ $p$

Debido a que el grado de es pequeño en comparación con , si el probador está haciendo trampa, entonces el verificador probablemente la atrapará (vea Wikipedia para la prueba, o resuélvalo usted mismo usando el lema de Schwartz-Zippel). $p$ $q$

Yuval Filmus
fuente

-1

Graficar el no isomorfismo en pruebas que no rinden más que su validez o todos los idiomas en NP tienen pruebas de conocimiento cero , Goldreich, Micali y Wigderson, JACM, 1991.

$G_1, G_2$ $i \in \{1,2\}$ $G_i$ $b \in \{1,2\}$

$b=i$

$\frac{1}{2}$

Vadym Fedyukovych
fuente

Proporcione una referencia adecuada a un artículo revisado por pares y un breve resumen del contenido. Los enlaces como el que proporciona tienden a romperse, y luego su respuesta contiene cero información.

Raphael

Pruebas interactivas para coNP

Respuestas: