Interaktywne dowody dla CoNP

9

Próbuję zrozumieć interaktywne systemy dowodowe i jako ćwiczenie wypróbowałem następujący problem. Wiemy toPHPSPACE 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 przezIP=PSPACE trasa) dla coNP?

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 coNPIPwymaga technik nierelatywizujących; jedynym znanym sposobem wykazania tego jest algebriacja, jak w odpowiedzi Yuvala. SeansIP=PSPACEjest 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

Odpowiedzi:

6

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

p(x1,,xk)=xk+1=01xn=01p(x1,,xn).
Protokół działa w następujący sposób:
  1. Prover wysyła weryfikatorowi liczbę pierwszą q(2n,2n+1), a ten ostatni to weryfikuje q jest liczbą pierwszą.
  2. Prover wysyła weryfikator p(z)Zq[z]. Weryfikator to weryfikujep(0)+p(1)=0i wysyła prover losowo r1.
  3. Prover wysyła weryfikator p(r1,z)Zq[z]. Weryfikator to weryfikujep(r1,0)+p(r1,1)=p(r1)i wysyła prover losowo r2.
  4. W końcu weryfikator dostaje p(r1,,rn)Zqi 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: G1,G2. Na początku każdej rundy strona weryfikująca wybiera indeksi{1,2} losowo i wysyła losową permutację wykresu Gi. Strona zapewniająca odpowiada indeksemb{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 12.

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