Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos (2000)
- Authors:
- Autor USP: TSUKIMOTO, EDSON TIHARU - IME
- Unidade: IME
- Sigla do Departamento: MAT
- Subjects: LÓGICA MATEMÁTICA; COMPUTABILIDADE E COMPLEXIDADE
- Language: Português
- Abstract: 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
- Imprenta:
- Data da defesa: 24.08.2000
-
ABNT
TSUKIMOTO, Edson Tiharu. Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos. 2000. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2000. Disponível em: https://teses.usp.br/teses/disponiveis/45/45131/tde-20210729-115809/. Acesso em: 23 abr. 2024. -
APA
Tsukimoto, E. T. (2000). Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45131/tde-20210729-115809/ -
NLM
Tsukimoto ET. Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos [Internet]. 2000 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45131/tde-20210729-115809/ -
Vancouver
Tsukimoto ET. Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos [Internet]. 2000 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45131/tde-20210729-115809/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
