• 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
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2000.tde-20210729-115809
Document
Auteur
Nom complet
Edson Tiharu Tsukimoto
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2000
Directeur
Titre en portugais
Uma prova da insolubilidade do Décimo Problema de Hilbert e relações com complexidade de algoritmos
Mots-clés en portugais
Computabilidade E Complexidade
Lógica Matemática
Resumé en portugais
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
Titre en anglais
not available
Resumé en anglais
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
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-07-29
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2022. Tous droits réservés.