Busca avançada
Ano de início
Entree

Aritmética de peano e caracterização de classes de complexidade computacional

Processo: 98/06230-6
Linha de fomento:Bolsas no Brasil - Doutorado
Vigência (Início): 01 de setembro de 1998
Vigência (Término): 31 de julho de 2002
Área do conhecimento:Ciências Exatas e da Terra - Matemática - Álgebra
Pesquisador responsável:Ricardo Bianconi
Beneficiário:Claus Akira Horodynski Matsushigue
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Assunto(s):Aritmética   Redes complexas   Teoria da demonstração

Resumo

O objetivo deste trabalho é estudar as relações existentes entre os problemas de Complexidade Computacional e os problemas em Teoria da Prova e Teoria dos Modelos da Aritmética de Peano e os seus fragmentos. Para tanto, esperamos caracterizar convenientemente as classes de complexidade via fragmentos da Aritmética de Peano de modo a nos permitir utilizar técnicas de indemonstrabilidade amplamente conhecidas da Lógica na Complexidade Computacional. (AU)