Projeto de pesquisa com o Newton e comigo

[Francisco Antonio Doria]

Newton e eu acabamos de publicar na Review of Behavioral Economics, editada pelo Barkley Rosser Jr. - ele é economista matemático - um artigo sobre o algoritmo de O'Donnell (que é conhecido desde 1979, e cujo comportamento muito se assemelha ao algoritmo de Babai, recentemente descrito). 

Nosso resultado central é um teorema condicional:

``Se PRA não prova P<NP, então há um algoritmo para qualquer problema NP (completo ou difícil) que é exponencial regulado pela função inversa da função de Ackermann.''

Encontramos o algoritmo de O'Donnell num preprint nunca publicado de dois matemáticos israelenses, Shai ben-David e Shai ha-Levi, e aí encontramos a referência ao artigo de O'Donnell (foi o Kreisel quem nos falou desse resultado). 

Gostaríamos de tentar implementá-lo. A dificuldade maior está na construção de uma máquina universal de Turing. Pensamos em construir essa máquina usando uma equação Diofantina universal, mas a coisa pode ficar muito complicada aí: que eu me lembre, uma das equações universais de mais baixo grau tem-no por volta de 70, com um número parecido de variáveis.

Alguem - que saiba programar - gostaria de nos ajudar nesse projeto? O que vai sair daqui será com certeza interessante. Se alguém se interessar pelo projeto, peço que me contacte em pvt.