P=NP: Perhaps I Change My Mind

[Joao Marcos]

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

[Francisco Antonio Doria]

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. 

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 logica-l+unsubscribe@dimap.ufrn.br.
Para postar neste grupo, envie um e-mail para logi...@dimap.ufrn.br.
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