Erros unilaterais em sistemas probabilísticos de prova

Na maioria dos sistemas de prova probabilística (teorema do PCP, por exemplo), as probabilidades de erro são geralmente definidas no lado dos falsos positivos, ou seja, uma definição típica pode parecer: se , o verificador sempre aceita, mas em outro caso, a probabilidade de rejeição é de pelo menos 1/2.$x \in L$

Existe um problema ao permitir que o erro ocorra do outro lado? Isso significa que o verificador sempre rejeita quando deveria e não faz mais do que um erro constante quando precisa aceitar. Outra possibilidade óbvia é permitir o erro de ambos os lados. Essas definições serão equivalentes às geralmente fornecidas? Ou eles se comportam de maneira diferente? Ou, nesse caso, existe um problema genuíno em permitir os erros do outro lado.

Permitir erro de completude não tem problema e é frequentemente considerado. Aqui estão algumas dicas .

Por outro lado, de um modo geral, a exclusão do erro de solidez remove significativamente o poder de um modelo.

No caso de sistemas interativos de prova, a proibição de erros de sonoridade torna a interação inútil, exceto na comunicação unidirecional de um provador para um verificador; isto é, IP com perfeição é igual a NP. Isso pode ser demonstrado considerando-se uma máquina NP que adivinha os bits aleatórios do verificador e a transcrição da interação que faz o verificador aceitar [FGMSZ89].

No caso de sistemas de prova probabilisticamente verificável (PCP), o mesmo raciocínio mostra que exigir uma sonoridade perfeita torna a aleatoriedade inútil para a escolha dos locais a serem consultados. Mais precisamente, pode ser demonstrado que PCP ( r ( n ), q ( n )) com perfeição c ( n ) e solidez perfeita (mesmo com consultas adaptativas) é igual à classe C dos problemas de decisão A = ( A _sim , A _não ) para o qual existe um idioma B 0,1 {0,1} * × {0,1} * × {0,1} * em P, de modo que

• Se x ∈ Um _sim , então Pr _{y ∈ {0,1} ^{r ( n )}} [∃ z ∈ {0,1} ^{q ( n )} tal que ( x , y , z ) ∈ B ] ≥ c ( n ), e
• se x ∈ A _não , então y ∀ {0,1} ^{r ( n )} ∀ z ∈ {0,1} ^{q ( n )} , ( x , y , z ) ∉ B ,

onde n = | x |. (Observe que, na definição da classe C , o caso yes não exige que um certificado inteiro seja preparado antes que o verificador selecione a sequência aleatória y , ao contrário da definição usual de um sistema PCP. Um certificado pode ser preparado depois de conhecer y , e somente a parte consultada do certificado é necessária, e é por isso que o comprimento de z é q ( n ).) Combinado com limites inferiores diretos, isso implica o seguinte:

• PCP (log, log) com perfeita solidez = P.
• PCP (poli, log) com perfeita solidez = RP .
• PCP (poli, poli) com perfeita solidez = NP.

Comparando-os com os teoremas do PCP PCP (log, O (1)) = NP e PCP (poli, O (1)) = NEXP, podemos ver que a exigência de som perfeito tem um enorme impacto.

[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser e Stathis Zachos. Sobre integridade e solidez em sistemas de prova interativos. In Randomness and Computation , vol. 5 of Advances in Computing Research , pp. 429-442, 1989. http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps