Neste seminário vamos apresentar o Teorema PCP, um resultado central da teoria da complexidade que conecta a verificação probabilística de provas à dureza de aproximação de problemas NP-difíceis. O capítulo explica que, depois da descoberta da NP-completude, os pesquisadores tentaram criar algoritmos eficientes para obter soluções aproximadas de problemas como MAX-3SAT ou Vertex Cover, mas as reduções tradicionais não bastavam para provar limites de aproximação. O Teorema PCP, formulado em 1992, resolveu essa limitação ao mostrar que NP = PCP(log n, 1), ou seja, que qualquer prova de pertencimento a NP pode ser verificada em tempo polinomial, consultando apenas um número constante de bits escolhidos aleatoriamente. Isso significa que é possível confirmar a validade de uma prova complexa observando apenas uma pequena amostra de seus bits — uma ideia surpreendente e poderosa. O capítulo também mostra que essa nova caracterização de NP é equivalente a afirmar que aproximar certas soluções NP-difíceis é tão difícil quanto resolvê-las exatamente. Por exemplo, o teorema implica que não existe algoritmo polinomial capaz de aproximar o MAX-3SAT além de uma razão fixa, a menos que P = NP. Essa relação entre provas probabilísticas e limites de aproximação abriu uma nova linha de pesquisa, permitindo demonstrar a inaproximabilidade de muitos problemas clássicos, como Independent Set e Vertex Cover. Assim, o Teorema PCP não apenas redefiniu a noção de prova na computação, mas também revolucionou nossa compreensão sobre os limites fundamentais da eficiência algorítmica.