Erreurs unilatérales dans les systèmes de preuve probabilistes

Dans la plupart des systèmes de preuve probabilistes (théorème PCP, par exemple), les probabilités d'erreur sont généralement définies du côté des faux positifs, c'est-à-dire qu'une définition typique pourrait ressembler à: si alors le vérificateur accepte toujours, mais dans les autres cas, la probabilité de rejet est d'au moins 1/2.$x \in L$

Existe-t-il un problème pour permettre à l'erreur de se produire de l'autre côté? Cela signifie que le vérificateur rejette toujours quand il le devrait et ne fait qu'une erreur constante lorsqu'il doit accepter. Une autre possibilité évidente consiste à autoriser l'erreur des deux côtés. Ces définitions seront-elles équivalentes à celle habituellement donnée? Ou, ils se comportent différemment? Ou d'ailleurs, y a-t-il un véritable problème à autoriser les erreurs de l'autre côté.?

Autoriser l'erreur d'exhaustivité n'a pas de problème et est souvent envisagé. Voici quelques conseils .

D'un autre côté, d'une manière générale, interdire l'erreur de solidité supprime considérablement la puissance d'un modèle.

Dans le cas des systèmes de preuve interactifs, interdire l'erreur de solidité rend l'interaction inutile, sauf pour la communication à sens unique d'un prouveur à un vérificateur; c'est-à-dire que IP avec une parfaite acoustique est égal à NP. Cela peut être démontré en considérant une machine NP qui devine les bits aléatoires du vérificateur et la transcription de l'interaction qui fait accepter le vérificateur [FGMSZ89].

Dans le cas des systèmes à preuve probabiliste vérifiable (PCP), le même raisonnement montre que l'exigence d'une parfaite intégrité rend l'aléatoire inutile pour choisir les emplacements à interroger. Plus précisément, on peut montrer que PCP ( r ( n ), q ( n )) avec l'exhaustivité c ( n ) et une parfaite intégrité (même avec des requêtes adaptatives) est égal à la classe C des problèmes de décision A = ( A _oui , A _non ) pour lequel il existe un langage B ⊆ {0,1} * × {0,1} * × {0,1} * dans P tel que

• si x ∈ A _oui , alors Pr _{y ∈ {0,1} ^{r ( n )}} [∃ z ∈ {0,1} ^{q ( n )} tel que ( x , y , z ) ∈ B ] ≥ c ( n ), et
• si x ∈ A _non , alors ∀ y ∈ {0,1} ^{r ( n )} ∀ z ∈ {0,1} ^{q ( n )} , ( x , y , z ) ∉ B ,

où n = | x |. (Notez que dans la définition de la classe C , le cas oui ne nécessite pas la préparation d'un certificat complet avant que le vérificateur ne sélectionne la chaîne aléatoire y , contrairement à la définition habituelle d'un système PCP. Un certificat peut être préparé après avoir connu y , et seule la partie interrogée du certificat est nécessaire, c'est pourquoi la longueur de z est q ( n ).) Combiné avec des limites inférieures simples, cela implique ce qui suit:

• PCP (log, log) avec une parfaite solidité = P.
• PCP (poly, log) avec une parfaite solidité = RP .
• PCP (poly, poly) avec une parfaite solidité = NP.

En les comparant aux théorèmes PCP PCP (log, O (1)) = NP et PCP (poly, O (1)) = NEXP, nous pouvons voir que l'exigence d'une parfaite solidité a un impact énorme.

[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser et Stathis Zachos. Sur l'exhaustivité et la solidité des systèmes de preuve interactifs. Dans Randomness and Computation , vol. 5 de Advances in Computing Research , pp. 429–442, 1989. http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps