Pesquisador da HP, publicou (2010) uma prova do famoso desafio matemático-computacional, provar que a classe de problemas P é igual à classe NP.
Muitas referências aí, começando pelo artigo do NYTimes Step 1: Post Elusive Proof. Step 2: Watch Fireworks que denuncia a manobra clássica: publicar uma prova difícil de verificar, aguardar o barulho em torno disso. Até me pergunto se a publicação por um pesquisador da HP não tem também a intenção de desviar atenção do escândalo da demissão do CEO da HP, por pagar despesas de viagem a sua secretária-modelo. Mas mesmo assim, e mesmo que a prova seja demonstrada falha, o que é muito possível, o simples fato de atacar um problema destes já abre caminhos incríveis em matemática e em computação.
Aliás, sem entrar em detalhes, que estão todos nas várias referências, P = NP é claramente problema fundamental em computação e em lógica, tem a ver com definir o que pode ser computado. Nada fácil.
P versus NP
P versus NP problem
A questão "P = NP?"
P vs NP Problem, Clay Institute, que oferece US$1.000.000 a quem resolver este problema, e alguns outros
P vs. NP for dummies, com boas referências e boa discussão
The history and status of the p versus np question, M/Sipser, http://www.win.tue.nl/~gwoegi/P-versus-NP/sipser.pdf exatamente o que o título propõe, completo, com histórico e questões matemáticas bem colocadas. 1989?
ResponderExcluirThe status of the p versus np question, http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext status atualizado, 2009.
Só uma correção... Deolalikar "provou" que P != NP, e não que P = NP
ResponderExcluirOps, muito bem observado, Leonardo. Obrigado pela correção. Já feita.
ResponderExcluir