Provas holográficas de tamanho quase-linear - Gouveia, Armando Ramos (1998)
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