Provas verificáveis probabilisticamente

Na teoria da complexidade computacional, uma prova verificável probabilisticamente (PCP) é um tipo de prova que pode ser verificada por um algoritmo aleatório usando uma quantidade limitada de aleatoriedade e ler um número limitado de bits da prova. O algoritmo é então obrigado a aceitar as provas corretas e rejeitar as provas incorretas com a probabilidade muito alta. Uma prova padrão (ou Certificada), como a usada na definição base do verificador de complexidade da classe NP, também satisfaz os requisitos, uma vez que o procedimento de verificação deterministicamente lê a prova toda, sempre aceita as provas corretas e rejeita as incorretas. No entanto, o que os torna interessante é a existência de provas verificáveis probabilisticamente que podem ser verificadas por ler apenas alguns bits da prova usando essencialmente a aleatoriedade.

Provas verificáveis probabilisticamente dão origem a muitas classes de complexidade dependendo do número de consultas necessárias e a quantidade de aleatoriedade utilizada. A classe PCP [r (n), q (n)] refere-se ao conjunto de problemas de decisão que têm provas verificáveis probabilisticamente que podem ser verificadas em tempo polinomial usando essencialmente, no máximo, r (n) bits aleatórios e pela leitura de no máximo q (n ) bits da prova . Exceto quando especificado ao contrário, as provas corretas devem ser sempre aceitas, e as provas incorretas devem ser rejeitadas com probabilidade maior que 1/2. O teorema PCP, melhor resultado na teoria da complexidade computacional, afirma que PCP [O (log n), O (1)] = NP.

A complexidade da classe PCP é a classe de decisão de problemas que têm provas probabilisticamente verificáveis com a completude 1, rigidez α <1, complexidade aleatória O (log n) e complexidade da consulta O (1).

Definição

O sistema de provas probabilisticamente verificáveis com completude c(n) e rigidez s(n) além do alfabeto Σ para um problema de decisão L, onde 0 ≤ s(n) ≤ c(n) ≤ 1, é um oráculo V (o verificador) que, sobre a entrada x e oráculo, acessa uma string π ∈ Σ^* (a prova), satisfaz as seguintes propriedades:

• Completude: Sex ∈ L então apara algum π, V^π(x) aceitar com a probabilidade de pelo menos c(n),
• Rigidez: Se x ∉ L então para todo π, V^π(x) aceitar com a probabilidade de no máximo s(n).

A complexidade randômica r(n) do verificador é o número máximo de bits aleatórios que V usa sobre tudo x de tamanho n.

Acomplexidade de consulta q(n)do verificador o número máximo de consultas que V faz a π sobre todo x de comprimento n.

O verificador é dito ser não-adaptável se ele faz todas as suas consultas antes de receber qualquer uma das respostas às perguntas anteriores.

A complexidade da classe PCP_c(n), s(n)[r(n), q(n)] é a classe de todas as decisões de problemas tendo o sistema de provas verificáveis probabilisticamente sobre o alfabeto de completude c(n) e rigidez s(n), onde o verificados é não adaptável, roda em tempo polinomial, e tem complexidade randômica r(n) e complexidade de consulta q(n).

A notação abreviada PCP [ r ( n), q ( n)] as vezes é usado para PCP _{1, ½} [ r ( n), q ( n)]. A complexidade da classe PCP_1, ½[O(logn), O(1)].

História e significado

A teoria de provas verificáveis probabilisticamente estuda o poder de sistemas de provas probabilisticamente verificáveis sob várias restrições dos parâmetros (integridade, solidez, complexidade da aleatoriedade, a complexidade da consulta e tamanho do  alfabeto.). Existem aplicações para a complexidade computacional (em especial, dificuldade de aproximação) e criptografia.

A definição de uma prova probabilisticamente verificável foi explicitamente introduzida por Arora e Safra em 1992, apesar de suas propriedades terem sido estudadas anteriormente. Em 1990 Babai, Fortnow e Lund provaram que PCP[P(n), P(n)] = NEXP, fornecendo a primeira equivalência não trivial entre provas normais (NEXP) e provas probabilisticamente verificáveis. O teorema PCP provado em 1992 afirma quePCP[O(log n),O(1)] = NP.

A teoria da dificuldade de aproximação exige uma compreensão detalhada do papel da completude, rigidez, tamanho do alfabeto e complexidade da consulta em provas verificáveis probabilisticamente.

Propriedades

Para configurações extremas dos parâmetros, a definição de provas probabilisticamente verificáveis é facilmente vista como sendo equivalente ao padrão de classes de complexidade. Por exemplo:

• PCP[0, 0] = P (P em sua definição possui aleatoriedade e acesso a prova.)
• PCP[O(log(n)), 0] = P (Um número logarítmico de bits aleatórios não ajudam uma máquina de Turing em tempo polinomial, desde que possa tentar randômicamente todas as possíveis strings de tamanho logarítmico em tempo polinomial.)
• PCP[0,O(log(n))] = P (Sem aleatoriedade, a prova pode ser tão difícil quanto uma string logarítmica de tamanho fixo. Uma máquina de turing em tempo polinomial pode testar todas as possíveis provas de tamanho logarítmico em tempo polinomial.)
• PCP[P(n), 0] = coRP (Pela definição de coRP.)
• PCP[0, P(n)] = NP (Pela definição de verificação baseada na definição de NP.)

O teorema PCP e MIP = NEXP pode ser caracterizado pelo seguinte:

• PCP[O(log n),O(1)] = NP (O teorema PCP)
• PCP[P(n),O(1)] = PCP[P(n),P(n)] = NEXP (MIP = NEXP).

Sabendo também que PCP[r(n), q(n)] ⊆ NTIME(2^O(r(n))q(n)+P(n)), se o verificador é forçado a ser não-adaptável. Para verificadores adaptáveis, PCP[r(n), q(n)] ⊆ NTIME(2^O(r(n)+q(n))+P(n)). Porém, se NP ⊆ PCP[o(log n),o(log n)] então P = NP.

Bibliografia

• Sanjeev Arora; Shmuel Safra. "Probabilistic checking of proofs: A new characterization of NP.", 45(1):70–122, 1998.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press (2008), ISBN 978-0-521-88473-0.
• Ryan O'Donnell e Venkatesan Guruswami. "A history of the PCP theorem".
• Predefinição:ComplexityZoo

Ligação externa

• Subhash Khot. anotações do curso de PCP. Universidade de New York, 2008.
• Ryan O'Donnell e Venkatesan Guruswami. anotações do curso de PCP. Universidade de Washington, 2005.