Интерактивные доказательства для coNP

Я пытаюсь понять интерактивные системы доказательства и попробовал следующую задачу в качестве упражнения. Мы знаем, что и , поэтому придумали (легко понять) интерактивные системы доказательства для ?$PH \subseteq PSPACE$$IP=PSPACE$$PH$

Интерактивная система доказательства для тривиальна, но мне не удалось получить интерактивную систему проверки даже для . Знаете ли вы о явной интерактивной системе доказательств (под явным, я имею в виду без прохождения маршрута ) для ?$NP$$coNP$$IP=PSPACE$$coNP$

Википедия описывает такой пример. Рассмотрим задачу UNSAT, полную coNP: учитывая CNF на n переменных, мы хотим убедить верификатора в том, что φ не является выполнимым. Мы арифметизируем ф к многочлену р и выберем некоторое большое простое число q . Пусть p ( x 1 , … , x k ) = 1 ∑ x k + 1 = 0 ⋯ 1 ∑ x n = 0 p ( x 1$\varphi$$n$$\varphi$$\varphi$$p$$q$ Протокол действует следующим образом:

1. Проверяющий отправляет верификатору простое число , и последнее проверяет, что q простое число.$q \in (2^n,2^{n+1})$$q$
2. Проверяющий отправляет верификатор . Верификатор проверяет, что p ( 0 ) + p ( 1 ) = 0 , и отправляет проверяющему случайное значение r 1 .$p(z) \in \mathbb{Z}_q[z]$$p(0) + p(1) = 0$$r_1$
3. Проверяющий отправляет верификатор . Верификатор проверяет, что p ( r 1 , 0 ) + p ( r 1 , 1 ) = p ( r 1 ) , и отправляет проверяющему случайный r 2 .$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$

Неизоморфизм графов в доказательствах, которые ничего не дают, кроме их валидности или всех языков в NP, имеют доказательства нулевого знания , Голдрайх, Микали и Вигдерсон, JACM, 1991.

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

$b=i$

$\frac{1}{2}$