Provas interativas para coNP

Estou tentando entender os sistemas interativos de provas e tentei o seguinte problema como exercício. Sabemos que $PH \subseteq PSPACE$ e $IP=PSPACE$ , então crie sistemas de prova interativos (fáceis de entender) para $PH$ ?

Um sistema de prova interativa para $NP$ é trivial, mas eu não conseguiu obter um sistema de prova interativa mesmo para $coNP$ . Sabe de um sistema de prova interativa explícita (por média explícita I sem passar pelo $IP=PSPACE$ rota) para $coNP$ ?

A Wikipedia descreve esse exemplo. Considere o problema UNSAT de coNP-completo: dado um CNF em n variáveis, queremos convencer o verificador de que φ não é satisfatório. Aritmizamos φ em um polinômio p e escolhemos um q primo grande . Seja p ( x 1 , … , x k ) = 1 ∑ x k + 1 = 0 ⋯ 1 ∑ x n = 0 p ( x 1$\varphi$$n$$\varphi$$\varphi$$p$$q$ O protocolo procede da seguinte maneira:

1. O provador envia ao verificador um primo , e o último verifica se q é primo.$q \in (2^n,2^{n+1})$$q$
2. O provador envia o verificador . O verificador verifica se p ( 0 ) + p ( 1 ) = 0 e envia ao provador um r 1 aleatório .$p(z) \in \mathbb{Z}_q[z]$$p(0) + p(1) = 0$$r_1$
3. O provador envia o verificador . O verificador verifica se p ( r 1 , 0 ) + p ( r 1 , 1 ) = p ( r 1 ) e envia ao testador um r 2 aleatório .$p(r_1,z) \in \mathbb{Z}_q[z]$$p(r_1,0) + p(r_1,1) = p(r_1)$$r_2$
4. $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$$p$

$p$$q$

Não-isomorfismo de gráfico em provas que produzem nada além de sua validade ou todos os idiomas no NP tem provas de conhecimento nulo , Goldreich, Micali e Wigderson, JACM, 1991.

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

$b=i$

$\frac{1}{2}$