• 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
 
 
Doctoral Thesis
DOI
https://doi.org/10.11606/T.45.2003.tde-20220712-120754
Document
Author
Full name
Claus Akira Matsushigue
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2003
Supervisor
Title in Portuguese
Indução de indemonstrabilidades e independências em Complexidade Computacional
Keywords in Portuguese
Computabilidade E Complexidade
Abstract in Portuguese
Obtemos que cada nível ('sigma POT.P IND.N' ou 'pi POT.N IND.N', com n < 'ômega') e a hierarquia polinomial completa (PH) são 'sigma IND.3'-completas. Também trabalhamos com asserções sobre tempo e espaço de Máquinas de Turing não-determinísticas e provamos que algumas delas são 'pi ind.1'- e 'sigma IND.2'-completas. Esses fatos fornecem peculiares resultados de independência em teorias T que são apenas axiomatizáveis e que conseguem codificar este tipo de asserção. Em particular, existe um problema de decisão L pertencente a 'sigma POT.P IND.N', ou PH, para o qual exatamente essa relaçãode pertinência é independente de T. Por outro lado, existe uma máquina de Turing que tem tempo não-determinístico polinomial, entretanto a veracidade dessa asserção também é independente de T. Ainda provamos que podemos obter alguns desses elementos independentes de um modo efetivo/construtível. Para isso, necessitamos demonstrar versões fortes de alguns teoremas da teoria da Recursão, tais como os Teoremas da Máquina de Turing Universal, da Parametrização (ou Smn, ou Indexador) e do Ponto Fixo, levando em conta loimites de tempo e/ou espaço não-determinísticos. Depois apresentamos de um modo mais objetivo o estudo da capacidade de se formalizar problemas da Teoria da Complexidade Computacional em Sistemas Lógicos Formais. Com efeito, dada uma teoria axiomatizável T, obtemos, grosso modo, que, para todos os problemas de decisão L, existe um modo de interpretar L em T de tal modo que a asserção 'L (nessa interpretação) pertence a um nível da hierarquia polinomial ('sigma POT.P IND.N' ou 'pi POT.P IND.N', com n < 'ômega')- ou à hierarquia inteira (PH)' é independente de T. Por outro lado, para todos os problemas de decisão L, existem Máquinas de Turing M e N (e interpretações de ambas em T) tais que o problema de decisão aceito por M e N é L e as duas asserções 'M tem tempo não-determinístico polinomial' e 'N não tem tempo não-determinístico polinomial' são indemonstráveis em T. Finalmente, algumas conseqüências envolvendo o problema P '? SOBRE DUAS BARRAS' NP puderam ser extraídas desses resultados. Obtivemos indemonstrabilidades referentes a esse problema em diversos pontos de vista. Desse modo, basicamente passamos a discutir o quão pequena poderia ser a capacidade de Sistemas Lógicos Formais (viz., teorias axiomatizáveis da Lógica Clássica de Primeira Ordem) para expressar corretamente as questões da Complexidade Computacional
Title in English
not available
Abstract in English
not available
 
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
2022-07-13
 
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-2024. All rights reserved.