Provas holográficas de tamanho quase-linear

• Ano de defesa: 1998
• Autor(a) principal: Gouveia, Armando Ramos
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Computabilidade E Complexidade
• Link de acesso: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021504/

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