skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

Uma introdução técnica relativa às provas robustas checáveis probabilisticamente

Matsushigue, Claus Akira

Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística 1997-07-10

Acesso online. A biblioteca também possui exemplares impressos.

  • Título:
    Uma introdução técnica relativa às provas robustas checáveis probabilisticamente
  • Autor: Matsushigue, Claus Akira
  • Orientador: Bianconi, Ricardo
  • Assuntos: Computabilidade E Complexidade; Matemática Aplicada
  • Notas: Dissertação (Mestrado)
  • Descrição: Na última década, vários tipos de sistemas de provas probabilísticas mostraram ter papel decisivo no desenvolvimento da Teoria da Ciência da Computação. Isto pode ser verificado pelo grande número de estudos acerca das provas interativas, provascom conhecimento-zero e provas transparentes (ou holográficas). Estes tópicos se norteiam pela robustez das codificações e pela capacidade computacional em checá-las. Buscamos, no texto, trazer uma introdução técnica relativa às provas robustaschecáveis probabilisticamente. Neste enfoque, a nova caracterização da classe não-determinística de tempo polinomial pela classe das Provas Checáveis Probabilisticamente formulada por Arora, Lund, Motwani, sudan e Szegedy em [ALM+92], NP =PCP(log n,1), é de importância central. Pretendemos provar tal caracterização, visto que ela perpassa os principais pontos do assunto e, ainda, abrange subjacentemente um grande ferramental computacional, algébrico e probabilístico, que éfundamental neste tópico. O teorema NP = PCP(log n, 1), tem no seu bojo a surpreendente propriedade que problemas de decisão em NP podem ser resolvidos por Máquinas de Turing de tempo polinomial no comprimento da entrada, se obtiverem ajuda deuma prova robusta (portanto, uma máquina não-determinística) e se puderem lançar moedas 'justas' (uma máquina probabilística). Entretanto, estas máquinas são restritas a só poderem ler um número logarítmico no comprimento da entrada de letras daprova robusta, sorteadas por um número constante de bits aleatórios, e têm uma probabilidade constante, e tão pequena quanto se queira, de aceitarem 'erradamente' uma entrada. Tendo como base o referido teorema, ou utilizando-se as suastécnicas, pode-se obter diversos resultados de inaproximabilidade de soluções ótimas. Assim, o texto também fornece um exemplo simples do uso das provas robustas checáveis probabilisticamente. Com ele, na Otimização Combinatória sabe-se ) hoje que os problemas MAX-SNP-difíceis não estão em PTAS ou, em outras palavras, não se pode obter a solução ótima, a menos de uma fração constante qualquer, com algoritmos de tempo polinomial, supondo-se P'DIFERENTE' NP
  • DOI: 10.11606/D.45.1997.tde-20210729-014911
  • Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
  • Data de criação/publicação: 1997-07-10
  • Formato: Adobe PDF
  • Idioma: Português
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.