Teorema PCP

Na teoria da complexidade computacional , o Teorema PCP afirma que todo problema de decisão na classe de complexidade NP tem provas checáveis probabilisticamente (prova que pode ser checada por um algoritmo aleatorizado) de complexidade de busca constante e complexidade logarítmica de aleatoriedade (usa um número logarítmico de bits aleatórios).

P Teorema PCP diz que para alguma constante universal K, para cada n, qualquer prova matemática de tamanho n pode ser reescrita como uma prova diferente de tamanho poli(n) que é formalmente verificável com 99% de precisão por um algoritmo aleatorizado que inspeciona apenas K letras daquela prova.

O Teorema PCP é a ideia fundamental da teoria da dificuldade de aproximação computacional , que investiga a dificuldade inerente ao projeto eficiente de aloritmos de aproximação para vários problemas de otimização.

O Teorema PCP diz que:

NP = PCP[O(log n), O(1)].

PCP e dificuldade de aproximação

Uma formulação alternativa do teorema PCP diz que a fração máxima de restrições satisfatíveis de um problema de satisfatibilidade de restrições é NP-difícil aproximar dentro algum fator constante.

Formalmente, para algumas contantes K e α < 1, o seguinte problema de promessa (Lsim, Lnão) é um problema de decisão NP-difícil:

  • Lsim = {Φ: todas as restrições em Φ são simultaneamente satisfatíveis}
  • Lnão = {Φ: toda atribuição satisfaz menos que uma fração α das restrições de Φ},

onde Φ é um problema de satisfatibilidade de restrições sobre um alfabeto Booleano com, nomáximo, K variáveis por restrição.

Como uma consequência desse teorema, pode ser mostrado que há soluções para vários problemas de otimização, incluindo a máxima satisfatibilidade de uma fórmula booleana, o máximo conjunto independente em grafos, e o problema do menor arranjo para reticulados não podem ser eficientemente aproximados a não ser que P = NP. Esses resultados são também chamados, algumas vezes, de teoremas PCP porque eles podem ser vistos como [[provas checáveis probabilisticamente] para NP com alguma estrutura adicional.

História

O Teorema PCP é a culminação de uma longa linha de trabalho em cima de prova interativas e provas checáveis probabilisticamente. O primeiro teorema relacionando provas padrão e provas checáveis probabilisticamente é a afirmação de que NEXP ⊆ PCP[poli(n), poli(n)], provado por Babai, Fortnow & Lund (1990).

Subsequentemente, o método usado nesse trabalho foi estendido por Babai, Fortnow, Levin, e Szegedy em 1991 (Babai et al. 1991), Feige, Goldwasser, Lund, Safra, and Szegedy (1991), e Arora e Safra em 1992 (Arora & Safra 1998) para produzir a prova do teorema PCP por Arora, Lund, Motwani, Sudan, e Szegedy em 1992 (Arora et al. 1998).

O Prêmio Gödel de 2001 foi entregue a Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, e Mario Szegedy pelo trabalho no teorema PCP e suas ligações com dificuldade de aproximação.

Em 2005 Irit Dinur uma prova diferente do teorema PCP, usando grafo expansores.[1]

Notas

  1. ↑ Ver a pré-impressão de 2005, Predefinição:ECCC. A versão autoritária do trabalho é Dinur (2007).

Refereências

  • Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), «Proof verification and the hardness of approximation problems», Journal of the ACM, 45 (3): 501–555, doi:10.1145/278298.278306 .
  • Arora, Sanjeev; Safra, Shmuel (1998), «Probabilistic checking of proofs: A new characterization of NP», Journal of the ACM, 45 (1): 70–122, doi:10.1145/273865.273901 .
  • Babai, László; Fortnow, Lance; Levin, Leonid; Szegedy, Mario (1991), «Checking computations in polylogarithmic time», STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing, ISBN 978-0-89791-397-3, ACM, pp. 21–32 .
  • Babai, László; Fortnow, Lance; Lund, Carsten (1990), «Nondeterministic exponential time has two-prover interactive protocols», SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, ISBN 978-0-8186-2082-9, IEEE Computer Society, pp. 16–25 .
  • Dinur, Irit (2007), «The PCP theorem by gap amplification», Journal of the ACM, 54 (3), doi:10.1145/1236457.1236459 .
  • Feige, Uriel; Goldwasser, Shafi; Lovász, László; Safra, Shmuel; Szegedy, Mario (1996), «Interactive proofs and the hardness of approximating cliques» (PDF), ACM, Journal of the ACM, ISSN 0004-5411, 43 (2): 268–292, doi:10.1145/226643.226652 .