• 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
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2000.tde-20210729-115809
Document
Author
Full name
Edson Tiharu Tsukimoto
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2000
Supervisor
Title in Portuguese
Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos
Keywords in Portuguese
Computabilidade E Complexidade
Lógica Matemática
Abstract in Portuguese
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
Title in English
not available
Abstract in English
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
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2021-07-29
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2022. All rights reserved.