Próbuję zrozumieć interaktywne systemy dowodowe i jako ćwiczenie wypróbowałem następujący problem. Wiemy to i , więc opracuj (łatwe do zrozumienia) interaktywne systemy próbne dla ?
Interaktywny system proof dla jest banalna, ale nie udało mi się nawet uzyskać interaktywnego systemu dowodowego . Czy znasz wyraźny interaktywny system dowodowy (przez wyraźny mam na myśli bez przechodzenia przez trasa) dla ?
complexity-theory
interactive-proof-systems
Shitikanth
źródło
źródło
Odpowiedzi:
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ć
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).
źródło
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ństwem12 .
źródło