Em um sistema de Provas Checáveis Probabilisticamente (PCP), o verificador consiste em uma Máquina de Turing de tempo polinomial, e deve checar uma demonstração de pertinência a uma dada linguagem. Tal demonstração chama-se prova holográfica e éfornecida por oráculo, isto é, uma máquina ilimitada computacionalmente. As provas corretas sempre são aceitas e a probabilidade de se aceitar uma prova incorreta é escolhida pelo verificador e pode ser tão pequena quanto se queira. Aroraet.al., com o famoso teorema 'NP = PCP (logn,1)', mostraram que se pode construir uma prova holográfica cuja verificação se faz com a consulta de um número constante de bits dessa prova e com o uso de O (logn) bits aleatórios, para entradas detamanho n. Uma melhora nesse resultado foi apresentada por Polishchuk e Spielman em 1994, que mostraram outra construção capaz de fornecer uma prova de tamanho quase-linear, a qual também é checável no esquema PCP (logn,1). Esta dissertaçãoexplica o que são as PCP's e mostra a construção dessas provas holográficas cujo tamanho é quase-linear

In a system of Probabilistical Checkable Proffs (PCP) the verifier consists of a Polynomial time Turing Machine and checks a proof of membership in a given language. This proof is called holographic proof and is given by an oracle, i.e., acomputationally unlimited machine. Correct proofs are always accepted and the probability of accepting an incorrect proof is chosen by the verifier an can be as low as desired. Arora et al., with the famous theorem 'NP = PCP(logn,1)', showedthat it possible to construct holographic proofs such that the verification is accomplished by reading a constant number of bits from the proof and by using O(logn) random bits, for inputs of lenght n. An improvement on this statement waspresented by Polishchuck and Spielman in 1994, they showed another construction that is able to yield a proof of nearly-linear size, which is also checkable in the PCP(logn,1) scheme. This dissertation explains what the PCP's are, and shows theconstruction of those nearly-linear size holographic proofs