Równoważność dwóch definicji kompletności i solidności w interaktywnych systemach dowodowych

11

Kompletność i solidność w interaktywnych systemach dowodowych są nieformalnie definiowane jako:

  • Kompletność: Jeśli stwierdzenie jest prawdziwe, szczery Prover może przekonać uczciwego weryfikatorem tego faktu WHP .

  • Poprawność: jeśli oświadczenie jest fałszywe, oszust nie może przekonać uczciwego weryfikatora (o ważności fałszywego oświadczenia)

Termin „bicz” jest albo interpretowany jako „z prawdopodobieństwem większym niż (powiedzmy) 2/3” lub „z prawdopodobieństwem większym niż odwrotność dowolnego wielomianu”. Wydaje się, że poniższa dyskusja nie ma znaczenia, jaką interpretację „bata” wybrać.

Najtrudniejszą częścią jest sposób obliczania prawdopodobieństwa: w niektórych źródłach prawdopodobieństwo przejmuje losowe monety zarówno przysłowia, jak i weryfikatora. W innych źródłach prawdopodobieństwo oblicza się tylko na podstawie losowych monet weryfikatora. To ostatnie jest zwykle uzasadnione jako: „bez względu na losowe monety provera, weryfikator podejmuje właściwą decyzję”.

Dla mnie obie definicje prawdopodobieństwa wydają się równoważne; ale nie mogę tego udowodnić. Czy mam rację? Czy możesz udowodnić, że są równoważne?

cc.complexity-theory interactive-proofs Niesamowite
źródło
2
powinieneś również rozważyć, czy masz na myśli monety „publiczne” czy „prywatne”. W ustawieniach monet publicznych zarówno prover, jak i weryfikator znają wyniki losowych wyborów, a dla monet prywatnych, prover nie zna losowych wyborów weryfikatora. W tym drugim przypadku zależy ci tylko na tym, co robi weryfikator, nie patrząc na provera, ponieważ prover po prostu nie zna losowych rzutów monetą.
Marcos Villagra
@Marcos: Spójrz na oryginalną definicję dowodów interaktywnych, która ma charakter „prywatny”. Ostatnie zdanie pierwszej kolumny na stronie 293, które zostało podkreślone, stwierdza, że ​​„prawdopodobieństwa są uwzględniane tylko w przypadku rzutów monetą B”. (Tutaj B jest weryfikatorem.) Z drugiej strony, wersja wyżej wymienionego czasopisma pozwala na przejęcie prawdopodobieństwa rzutów monetą obu stron. To może być źródłem zamieszania, prawda?
MS Dousti
@Sadeq: Rozumiem, nie wiedziałem o tej różnicy między wersją czasopisma a wersją konferencji. Jednak w przypadku monet prywatnych nie widzę sensu, biorąc pod uwagę rzuty monetą prover, ponieważ mógł zdecydować, że nie powie o tym weryfikatorowi. Weryfikator odpowiada za decyzję o przyjęciu lub odrzuceniu i może nie wiedzieć, co robi łowca.
Marcos Villagra
1
@Marcos: Masz rację, ale to samo rozumowanie dotyczy dowodów monet publicznych; ponieważ w tych systemach rzuty monetą prover są nadal prywatne (tylko monety weryfikatora są publiczne). Ogólnie rzecz biorąc, można rozważyć deterministycznego przysłowia: ponieważ jest on wszechmocny, nie potrzebuje losowości i może wybrać optymalną odpowiedź deterministycznie. Jednak tego rodzaju rozumowanie nie działa, jeśli weźmiemy pod uwagę systemy zerowej wiedzy, w których strategia provera powinna być probabilistyczna (w przeciwnym razie jego wiedza wyciekłaby).
MS Dousti
2
(Ciąg dalszy) Jeśli losownik jest randomizowany, myślę, że właściwym sformułowaniem jest obliczenie prawdopodobieństwa na podstawie obu rzutów monetą weryfikatora: Podczas gdy, jak powiedział Marcos, weryfikator odpowiada za ostateczną decyzję, jej decyzja jest wykonane (między innymi) na podstawie wiadomości pochodzących od przysłowia. Biorąc pod uwagę fakt, że jest on losowy, jego rzuty monetami z pewnością wpływają na wysyłane przez niego wiadomości. Dlatego rzuty monetą provera wpływają na prawdopodobieństwo przyjęcia. Czy mam rację?
MS Dousti

Odpowiedzi:

6

Przysłowie jest „wszechmocny i posiada nieograniczone zasoby obliczeniowe”, więc nie potrzebuje losowych bitów. Zatem jedyną przypadkowością jest losowość weryfikatora.

Jeśli przysłowie używa losowych bitów, powinien je zastąpić losowym ciągiem bitów, który najprawdopodobniej sprawi, że weryfikator zaakceptuje (dotyczy to zarówno uczciwego, jak i nieuczciwego przysłowia). Ponadto, przysłowie może określić ten optymalny ciąg bitów, ponieważ jest on „wszechmocny”.

Tyson Williams
źródło
1
Jak powiedziałem w powyższym komentarzu, jest to prawdą tylko wtedy, gdy weźmiesz pod uwagę tylko interaktywne dowody. Jednak rzeczy są bardzo różne, jeśli weźmiesz pod uwagę inne właściwości, takie jak „zerowa wiedza”, która jest naturalnie związana z dowodami interaktywnymi.
MS Dousti
1
Kontynuacja: W szczególności Oren udowodnił, co następuje: „... zgodnie z definicją zerowej wiedzy wejściowej losowość dowodu jest niezbędna do nietrywialności systemów dowodowych zerowej wiedzy. Innymi słowy, każdy język który ma pomocniczy system zerowej wiedzy z wejściami pomocniczymi, w którym przysłowie jest deterministyczne w stosunku do BPP. ” (Aby uzyskać więcej informacji, zobacz rozdział 4.5 Oren .) Dlatego nie zawsze można założyć, że P jest deterministyczne.
MS Dousti