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

• Processo: 98/06230-6
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de setembro de 1998
• Data de Término da vigência: 31 de julho de 2002
• Área de 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
• Palavra(s)-Chave do Pesquisador: Aritmetica | Complexidade | Demonstrabilidade | Modelos | Np=Co-Np | P=Np

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)