Detalhes bibliográficos
| Ano de defesa: |
1997 |
| Autor(a) principal: |
Matsushigue, Claus Akira |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| 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
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-014911/
|
Resumo: |
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 |
