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. -- Você está recebendo esta mensagem porque se inscreveu no grupo "LOGICA-L" dos Grupos do Google. Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para [email protected]. Para postar neste grupo, envie um e-mail para [email protected]. Visite este grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/. Para ver esta discussão na web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7B%2BR7ciAjcvJU3V4F0kFHfYK3XKU6oV25sNJhOQTt5Fs_w%40mail.gmail.com.
