Błędy jednostronne w probablistycznych systemach dowodowych

W większości probabilistycznych systemów dowodowych (na przykład twierdzenie PCP) prawdopodobieństwa błędów są zwykle definiowane po stronie fałszywie dodatnich, tj. Typowa definicja może wyglądać tak: jeśli to weryfikator zawsze przyjmuje, ale w w innym przypadku prawdopodobieństwo odrzucenia wynosi co najmniej 1/2. $x \in L$

Czy istnieje problem z dopuszczeniem wystąpienia błędu po drugiej stronie? Oznacza to, że weryfikator zawsze odrzuca, kiedy powinien, i robi tylko stały błąd, gdy musi zaakceptować. Inną oczywistą możliwością jest dopuszczenie błędu po obu stronach. Czy te definicje będą równoważne definicji zwykle podawanej? Czy zachowują się inaczej? A jeśli tak, to czy istnieje prawdziwy problem z dopuszczeniem błędów po drugiej stronie.?

cc.complexity-theory pcp interactive-proofs

— Arnab
źródło

Dlaczego głosowanie negatywne? Niektóre PCP nie mają doskonałej kompletności. Z drugiej strony istnieją pewne redukcje o doskonałej solidności, ale nie doskonałej kompletności („Darmowe bity itp.”, Bellare + Goldreich + Sudan, s. 21, ostatni akapit).

— Yuval Filmus,

@Yuval Filmus: Istnieje wiele wersji wspomnianego papieru. Do której wersji się odnosisz?

— Tsuyoshi Ito,

Bardzo dziękuję wam obojgu za odpowiedzi. Wydaje mi się, że opinia negatywna pochodzi z przekonania, że nie jest to pytanie „badawcze”. To nie jest prawda. W każdym razie, nie mogę nawet głosować za odpowiedzią z moim wynikiem reputacji, który dzisiaj został nawet zmniejszony :)

— Arnab

@TsuyoshiIto W wersji 2 znajduje się na dole strony 22 (strona 24 pliku).

— Yuval Filmus,

Nie mam pojęcia. Właśnie przejrzałem „idealną solidność”.

— Yuval Filmus

Dopuszczenie błędu kompletności nie stanowi problemu i często jest brane pod uwagę. Oto kilka wskazówek .

Z drugiej strony, ogólnie mówiąc, niedopuszczenie błędu dźwiękowego znacznie usuwa moc modelu.

W przypadku interaktywnych systemów dowodowych niedopuszczenie błędu dźwiękowego powoduje, że interakcja jest bezużyteczna, z wyjątkiem jednokierunkowej komunikacji od weryfikatora do weryfikatora; to znaczy, IP o doskonałej głośności jest równy NP. Można to pokazać, rozważając maszynę NP, która zgaduje losowe bity weryfikatora oraz transkrypcję interakcji, która sprawia, że weryfikator akceptuje [FGMSZ89].

W przypadku systemów probabilistycznie sprawdzalnych (PCP) to samo rozumowanie pokazuje, że wymaganie doskonałej dźwiękowości sprawia, że losowość jest bezużyteczna przy wyborze lokalizacji do zapytania. Dokładniej, można wykazać, że PCP ( r ( n ), q ( n )) z kompletnością c ( n ) i doskonałą solidnością (nawet przy zapytaniach adaptacyjnych) jest równy klasie C problemów decyzyjnych A = ( A _tak , A _no ), dla którego istnieje język B ⊆ {0,1} * × {0,1} * × {0,1} * w P, taki że

jeśli x ∈ A _tak , to Pr _{y ∈ {0,1} ^{r ( n )}} [∃ z ∈ {0,1} ^{q ( n )} takie, że ( x , y , z ) ∈ B ] ≥ c ( n ), i
jeśli x ∈ A _nie , to ∀ y ∈ {0,1} ^{r ( n )} ∀ z ∈ {0,1} ^{q ( n )} , ( x , y , z ) ∉ B ,

gdzie n = | x |. (Należy zauważyć, że w definicji klasy C przypadek „tak” nie wymaga przygotowania całego certyfikatu, zanim weryfikator wybierze losowy ciąg y , w przeciwieństwie do zwykłej definicji systemu PCP. Certyfikat można przygotować po znajomości y i potrzebna jest tylko kwerenda części certyfikatu, dlatego długość z wynosi q ( n ).) W połączeniu z prostymi dolnymi granicami oznacza to:

PCP (log, log) o doskonałej solidności = P.
PCP (poli, log) o doskonałej solidności = RP .
PCP (poli, poli) o doskonałej solidności = NP.

Porównując je z twierdzeniami PCP PCP (log, O (1)) = NP i PCP (poli, O (1)) = NEXP, widzimy, że wymaganie doskonałej solidności ma ogromny wpływ.

[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser i Stathis Zachos. O kompletności i solidności w interaktywnych systemach proof. W Randomness and Computation , tom. 5 z Advances in Computing Research , str. 429–442, 1989. http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps

— Tsuyoshi Ito
źródło