• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2000.tde-20210729-115809
Documento
Autor
Nome completo
Edson Tiharu Tsukimoto
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2000
Orientador
Título em português
Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos
Palavras-chave em português
Computabilidade E Complexidade
Lógica Matemática
Resumo em português
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
Título em inglês
not available
Resumo em inglês
Hilbert, in his Tenth Problem, questioned whether there would exist an effective procedure which decided if a given diofantine equation has solution. In this work, we will present a proof, published in the seventies by Yuri Matyasevic which states that such an effective procedure does not exist. We will also show that the above result has implications with the theory of complexity of algorithms. Precisely, we will see that if the proof of the unsolvability of the Hilbert's Tenth Problem can be stated in a certain fragment of the Peano's Arithmetic, in a certain sense we are going to make precise, then NP=coNP
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2021-07-29
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2022. Todos os direitos reservados.