Resolvido o duelo entre P e NP?

Estadão

09 Agosto 2010 | 11h15

O tema já apareceu duas vezes na minha frente hoje (uma num comentário à postagem que fiz tempos atrás sobre Alan Turing, outra no twitter do físico @Dbohr), então acho que vale a pena tocar no assunto aqui, mesmo as coisas estando ainda num estágio bem preliminar — e, como de costume, com detalhes técnicos bem acima da minha competência pessoal.

Surgiu na internet, do domingo, um artigo de um pesquisador da HP que pode ser a prova da solução de um dos maiores problemas ainda em aberto da matemática — a questão de se P é igual ou não a NP. Esse problema é um dos Desafios do Milênio do Instituto Clay, para cada um dos quais existe um prêmio de US$ 1 milhão.

(Na verdade, a questão surgiu três vezes na minha frente nas últimas 24 horas: ontem à noite ela estava num episódio de Numb3rs a que assisti no DVD)

Agora, seria bom, claro, saber do que estamos falando quando nos referimos a “P” e “NP”. Essas duas categorias se referem a tipos de problemas. Um problema tipo “P” é um para o qual existe um procedimento simples para se descobrir a solução.

Por exemplo, se eu lhe pedir para somar 2285 a 1274, existe um algoritmo muito famoso, que todos aprendemos lá pelos 7 anos de idade, que permite chegar, sem grande dificuldade, ao resultado 3559.

Já um problema “NP” é  um para o qual é muito mais fácil checar se uma proposta de solução é correta do que construir uma solução a partir do zero.

Se eu lhe pedir para encontrar os fatores primos de 12.709.189, você não terá muita escolha além de testar a divisibilidade do número sucessivamente por 2, 3, 5, 7, 11, 13… Já se eu lhe disser que os fatores em questão são 3571 e 3559, você só precisará de alguns segundos para testar minha solução.

Existe, no entanto, a possibilidade que os problemas NP não passem de problemas P disfarçados. Se isso  for verdade, significará que problemas que hoje em dia só podem ser enfrentados numa base caso a caso e por métodos de força bruta, por tentativa e erro, na verdade têm soluções mais rápidas e gerais.

Muitas questões que hoje requerem  supercomputadores para serem tratadas talvez possam ser reduzidas a procedimentos aplicáveis em calculadoras de bolso; quem sabe exista até um método  perfeito e imbatível para escolher jogadas no xadrez.

A prova apresentada por Vinay Deolalikar, no entanto, afirma o contrário: P não é NP. Ele está certo? Fiquem ligados…