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

not available