Blog do Pablo Ximenes

O pesquisador da HP, Vinay Deolalika, demonstra em um paper de 100 páginas uma possível prova de que P != NP, resolvendo o mais famoso problema em aberto da ciência da computação. Apesar de reputada como uma tentativa séria, a prova ainda passará pelo escrutínio da comunidade científica antes que possamos considerar a questão fechada. O problema é parte da relação de problemas do Millenium Prize. Ou seja, se a prova for considerada válida, o cientista ganhará a recompensa de um milhão de dólares. Segundo as palavras do famoso pesquisador Stephen Cook, “isso parece uma alegação razoavelmente séria de uma solução para o problema P vs. NP”.

O paper de 100 paginas pode ser encontrado aqui.

Abaixo, o email de divulgação enviado pelo autor da prova:

Dear Fellow Researchers,

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof. Second to this were the technical hurdles faced at each stage in the proof This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work Comments and suggestions for improvements to the paper are highly welcomed.

Fonte: http://gregbaker.ca/blog/2010/08/07/p-n-np/