Quando se fizer a história deste problema, vai se ver que muitos resultados interessantes foram esquecidos e redescobertos muitas vezes. Já falei aqui no algoritmo de O'Donnell, de 1979, por aí, que satisfaz ao seguinte teorema: ``se P<NP não é demonstrável pela PRA, aritmética primitivo-recursiva, então existe para a solução de problemas da classe NP um algoritmo quase polinomial, que cresce no tempo como a exponencial do inverso da função de Ackermann.'' Para todos os efeitos práticos, é polinomial.
Me parece que tal algoritmo vem de encontro a esse resultado antigo de O'Donnell. On Tue, Dec 12, 2017 at 5:40 AM, Joao Marcos <[email protected]> wrote: > P=NP: Perhaps I Change My Mind > https://rjlipton.wordpress.com/2017/12/08/pnp-perhaps-i-change-my-mind/ > > * * * > > With an incidental quote, of independent interest: > "Simply put, a proof is a method of establishing truth. Like beauty, > “truth” sometimes depends on the eye of the beholder, and it should > not be surprising that what constitutes a proof differs among fields." > > * * * > > JM > > -- > 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/CAO6j_LjGCEi1sK9AOq%3Dv4gSbzs34nwVzeQE0j% > 3DZ993wkDZ79bg%40mail.gmail.com. > -- fad ahhata alati, awienta Wilushati -- 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%2BziYgmS8RnCNW7FQLWRpWFCD9JNL%2BA_t52O4kvYgttMg%40mail.gmail.com.
