Exportar registro bibliográfico

Provas holográficas de tamanho quase-linear (1998)

  • Authors:
  • Autor USP: GOUVEIA, ARMANDO RAMOS - IME
  • Unidade: IME
  • Sigla do Departamento: MAP
  • Assunto: COMPUTABILIDADE E COMPLEXIDADE
  • Language: Português
  • Abstract: 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
  • Imprenta:
  • Data da defesa: 13.11.1998
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      GOUVEIA, Armando Ramos; KOHAYAKAWA, Yoshiharu. Provas holográficas de tamanho quase-linear. 1998.Universidade de São Paulo, São Paulo, 1998. Disponível em: < https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021504/ >.
    • APA

      Gouveia, A. R., & Kohayakawa, Y. (1998). Provas holográficas de tamanho quase-linear. Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021504/
    • NLM

      Gouveia AR, Kohayakawa Y. Provas holográficas de tamanho quase-linear [Internet]. 1998 ;Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021504/
    • Vancouver

      Gouveia AR, Kohayakawa Y. Provas holográficas de tamanho quase-linear [Internet]. 1998 ;Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-021504/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

    Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021