Solução para maior problema da computação está provavelmente errada

Divulgada inicialmente como a solução para a maior questão na ciência da computação, a mais recente tentativa de resolver o problema "P vs. NP" está agora sendo questionada.

Dois importantes cientistas da computação encontraram "falhas fatais" na versão da prova apresentada por Vinay Deolalikar, funcionário dos Laboratórios Hewlett-Packard em Palo Alto, na Califórnia.

Desde que a prova de cem páginas foi divulgada na internet na semana passada, matemáticos e cientistas da computação estão em uma luta contra o tempo tentando entendê-la.

O problema está relacionado à velocidade com que um computador consegue completar tarefas como a fatoração de números. Grosso modo, "P" é o conjunto de problemas que pode ser computado rapidamente, enquanto "NP" contem os problemas cujas respostas podem ser checadas rapidamente, mas não resolvidos rapidamente do zero.

Suspeitava-se que P fosse diferente de NP (P =/= NP). Se isso for verdade, imporia limites severos na capacidade de processamento de computadores. Deolalikar afirma ter provado isso. Se sua prova estiver correta, ele ganhará o Prêmio do Milênio, de US$ 1 milhão (R$ 1,78 milhão), oferecido pelo Instituto Clay de Matemática, sediado em Cambridge, Massachusetts.

BURACO SÉRIO

Grande parte da animada discussão on-line sobre a prova aconteceu no blog de Richard Lipton, um cientista da computação do Instituto de Tecnologia da Geórgia, EUA. Lipton tem 30 anos de experiência na questão "P vs. NP".

Hoje de manhã, porém, Lipton postou um e-mail de outro cientista, Neil Immeman, da Universidade de Massachusetts, EUA, que afirma ter encontrado um "sério buraco" no artigo de Deolalikar.

O principal argumento de Immerman seria um erro nas hipóteses quando tentou descrever o conjunto P de uma determinada maneira. Deolalikar tenta mostrar que alguns problemas estão em NP, mas não em P - o que demonstraria que P=/= NP - invocando outro conjunto matemático conhecido como FO.

Immerman diz que esse conjunto não pode ser usado dessa forma por causa de outros métodos usados na prova.

Como todos problemas matemáticos famosos, tentativas de resolver "P vs. NP" são comuns, mas poucas são levadas a sério porque não tendem a ter fundamentos teóricos fortes.

A empolgação com a prova de Deolalikar parece ter sido estimulada por seu status profissional como pesquisador da HP e por um comentário de Stephen Cook, da Universidade de Toronto, formulador do problema "P vs. NP", que afirmou que o trabalho de Deolalikar parecia ser uma "asserção relativamente séria".

TRÊS CENÁRIOS

Ao comentar sobre o blog de Lipton alguns dias atrás, Terence Tao, da Universidade da Califórnia em Los Angeles, propôs três cenários a respeito da correção da prova.

No melhor caso, pequenas mudanças consertariam o argumento de Deolalikar e provariam de uma vez por todas que P =/= NP. Outra possibilidade é que grandes mudanças no argumento poderiam ainda salvar a prova. Por fim, a estratégia de prova geral de Deolalikar poderia fornecer subsídios para tentativas futuras de provar o argumento.

Tao continuou afirmando que os dois primeiros cenários são improváveis, mas o terceiro ainda não estava resolvido.

Mesmo que as críticas estejam corretas, o incidente como um todo pode ainda estimular descobertas matemáticas. Uma página wiki foi montada onde é possível postar opiniões sobre a prova de Deolalikar. Comentários variam de correções de pequenas erros de digitação a críticas detalhadas dos métodos matemáticos empregados.

Essa efervescência de atividade on-line sugere que um novo modo de fazer matemática pode estar surgindo, com blogs e wikis rivalizando com quadros negros e revistas científicas - um resultado potencialmente positivo, mesmo que a questão do "P vs. NP" continue sem solução.

"A internet está fazendo uma enorme diferença na forma como os matemáticos operam", diz Timothy Gowers, da Universidade de Cambridge. "Um processo que poderia ter levado semanas e semanas ocorreu muito rapidamente."

FONTE: FOLHA ONLINE / DA NEW SCIENTIST
 
Notícia divulgada em 13/08/2010