Interaktywne dowody dla CoNP

9

Próbuję zrozumieć interaktywne systemy dowodowe i jako ćwiczenie wypróbowałem następujący problem. Wiemy to $PH \subseteq PSPACE$ i $IP=PSPACE$ , więc opracuj (łatwe do zrozumienia) interaktywne systemy próbne dla $PH$ ?

Interaktywny system proof dla $NP$ jest banalna, ale nie udało mi się nawet uzyskać interaktywnego systemu dowodowego $coNP$ . Czy znasz wyraźny interaktywny system dowodowy (przez wyraźny mam na myśli bez przechodzenia przez $IP=PSPACE$ trasa) dla $coNP$ ?

complexity-theory interactive-proof-systems

— Shitikanth
źródło

Czy możesz wyjaśnić, co masz na myśli przez interaktywny system dowodowy? Dla tych, którzy nie znają tego terminu.

— jmite

3

Nawet włączenie

c o N P \subseteq I P

$coNP \subseteq IP$ wymaga technik nierelatywizujących; jedynym znanym sposobem wykazania tego jest algebriacja, jak w odpowiedzi Yuvala. Seans

I P = P S P A C E

$IP=PSPACE$ jest jedynie niewielką modyfikacją techniczną tego dowodu.

— sdcvvc,

2

@sdcvvc, myślę, że twój komentarz wart jest opublikowania jako odpowiedzi. Wyjaśnia, dlaczego nie ma tak prostych przykładów jak te dla NP.

— Kaveh

6

Wikipedia przedstawia taki przykład. Rozważ problem z całkowitym koNP: UNSAT: biorąc pod uwagę CNF $\varphi$ na $n$ zmienne, chcemy przekonać weryfikatora, że $\varphi$ nie jest zadowalające. Arytmetyzujemy $\varphi$ na wielomian $p$ i wybierz dużą liczbę pierwszą $q$ . Pozwolić

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).$ Protokół działa w następujący sposób:

Prover wysyła weryfikatorowi liczbę pierwszą $q \in (2^n,2^{n+1})$ , a ten ostatni to weryfikuje $q$ jest liczbą pierwszą.
Prover wysyła weryfikator $p(z) \in \mathbb{Z}_q[z]$ . Weryfikator to weryfikuje $p(0) + p(1) = 0$ i wysyła prover losowo $r_1$ .
Prover wysyła weryfikator $p(r_1,z) \in \mathbb{Z}_q[z]$ . Weryfikator to weryfikuje $p(r_1,0) + p(r_1,1) = p(r_1)$ i wysyła prover losowo $r_2$ .
W końcu weryfikator dostaje $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$ i sprawdza, czy ma poprawną wartość, oceniając $p$ bezpośrednio.

Ponieważ stopień $p$ jest mały w porównaniu do $q$ , jeśli łowczyni oszukuje, weryfikator prawdopodobnie ją złapie (dowód można znaleźć na Wikipedii lub samemu go opracuj, używając lematu Schwartza-Zippela).

— Yuval Filmus
źródło

-1

Wykres nie-izomorfizm przy dowodach, które dają nic, ale ich ważność lub wszystkie języki w NP mają zerowe dowody , Goldreich, Micali i Wigderson, JACM, 1991.

Wspólne dane wejściowe to para wykresów: $G_1, G_2$ . Na początku każdej rundy strona weryfikująca wybiera indeks $i \in \{1,2\}$ losowo i wysyła losową permutację wykresu $G_i$ . Strona zapewniająca odpowiada indeksem $b \in \{1,2\}$ .

Właściwość kompletności: w przypadku grafów nieizomorficznych przysłowia zawsze dają prawidłową odpowiedź $b=i$ .

Soundness: w przypadku grafów izomorficznych, przysłowia dają prawidłową odpowiedź z prawdopodobieństwem $\frac{1}{2}$ .

— Vadym Fedyukovych
źródło

Podaj odpowiednie odniesienie do recenzowanego artykułu i krótkie streszczenie treści. Linki takie jak ten, które podajesz, zwykle się psują, a wtedy twoja odpowiedź zawiera zero informacji.

— Raphael