Detalhes bibliográficos
| Ano de defesa: |
2000 |
| Autor(a) principal: |
Tsukimoto, Edson Tiharu |
| 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/45131/tde-20210729-115809/
|
Resumo: |
Em seu Décimo Problema, Hilbert indaga se existe um procedimento efetivo que decida se uma dada equação diofantina admite solução. Neste trabalho vamos mostrar uma prova, finalizada por Yuri Matyasevic na década de setenta, de que tal procedimento efetivo não existe. Ao final, mostraremos como esse resultado tem relações com a teoria de complexidade de algoritmos. Mais especificamente, veremos que se a demonstração da insolubilidade do Décimo Problema de Hilbert puder ser formalizada em um certo fragmento da aritmética de Peano, em um sentido que iremos precisar, então NP=coNP |
