Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.2000.tde-20210729-115809
Documento
Autor
Nombre completo
Edson Tiharu Tsukimoto
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2000
Director
Título en portugués
Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos
Palabras clave en portugués
Computabilidade E Complexidade
Lógica Matemática
Resumen en 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 en inglés
not available
Resumen en 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
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-07-29