Błędy jednostronne w probablistycznych systemach dowodowych

10

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∈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,
1
Nie mam pojęcia. Właśnie przejrzałem „idealną solidność”.
Yuval Filmus

Odpowiedzi:

12

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