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 issofor 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 requeremsupercomputadores para serem tratadas talvez possam ser reduzidas a procedimentos aplicáveis em calculadoras de bolso; quem sabe exista até um métodoperfeito 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...
