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)].