vinay deolalikar está propondo uma prova de que P~=NP. este é um dos mais radicais e importantes problemas da ciência da computação e, se resolvido, vai mudar o mundo. principalmente se deolalikar estiver errado e alguém conseguir provar justamente o contrário do que ele está propondo.
um monte de gente muito inteligente e dedicada está tentando provar que ou P=NP ou P~=NP há décadas. mas toda vez que alguém aparece com uma suposta prova, muito mais gente aparece com objeções a ela. não está sendo diferente com a “prova” de deolalikar.
a versão da prova publicada no 6 de agosto está neste link. são mais de cem páginas da matemática mais complexa que existe. o miolo da prova deveria ser o teorema abaixo. boa leitura. da cópia, aliás, porque deolalikar retirou o original de sua página e “está trabalhando em correções”, segundo fontes próximas. há quem acredite que a prova já era, foi só um sonho que durou tres dias.
se você quiser saber mais sobre o problema em questão, este blog escreveu sobre o assunto em março de 2008, quando se tratava da existência de uma possível prova de que P=NP… o contrário do que deolalikar diz ter provado. o texto está replicado abaixo exatamente como apareceu e –logo depois-desapareceu, quando o TERRA trocou a plataforma de publicação, dando conta de que um professor da UFPE, em recife, talvez tivesse resolvido o problema.
a complexidade computacional de um problema é, em última análise, o tempo que se gasta, no pior caso, para resolvê-lo. problemas computacionais são resolvidos em computadores, usando algoritmos, que são seqüências de instruções bem definidas, que o computador [qualquer que seja] pode executar de forma precisa. por trás deste blog, há um conjunto de algoritmos, sendo executados por servidores no terra.com.br, para transformar os tecles e clicks do leitor em páginas visualizadas na tela.
algoritmos estão, na verdade, por trás de quase tudo o que acontece no mundo. o motor flex depende de algoritmos para analisar o resultado da compbustão e sintonizar o motor para a mistura de combustível que está no tanque. seu banco -on e off line- é uma montanha de algoritmos. assim como o sistema de saúde, o imposto de renda, a tv digital… o voar dos aviões, o sistema de controle de tráfego aéreo e por aí vai. não, os pássaros ainda não são informatizados e seu voar é livre. por enquanto.
pois bem. os problemas computacionais do tipo P são aqueles em que o tempo [ou o custo] para tratar uma instância qualquer do problema é, no máximo, de ordem polinomial. algo como o tamanho do problema elevado ao quadrado, por exemplo. ou o tamanho do problema multiplicado pelo logaritmo dele mesmo, que vem a ser a complexidade de ordenar um arquivo qualquer [ou de começar com uma lista desordenada de palavras e deixá-la, ao fim do algoritmo, ordenada].
há problemas cuja complexidade de solução depende de uma função não polinomial do tamanho da entrada, como seu fatorial [n! = 1* 2 * 3 * … * n]. gerar todas as permutações de um conjunto de N números gasta tempo N!, onde exclamação, aí atrás, é o símbolo para fatorial. que vem a ser uma função que cresce muito depressa. quer ver? se um problema tem complexidade fatorial e seu tamanho é 3 [três objetos como entrada…], o custo de resolvê-lo é 6 [pois 1 * 2 * 3 = 6]. tamanho 4 custa 24, 5 custa 120, 6 custa 720, 7 já vai pra 5040… e, se o problema for de tamanho 20, o custo é nada menos do que 2.432.902.008.176.640.000! quase dois e meio quintilhões. coisa de louco. isso faz com que problemas para os quais não se conhece uma solução polinomial sejam, via de regra, considerados computacionalmente intratáveis.
até aqui, dá pra entender o que são os problemas do tipo P: aqueles para os quais -mesmo em seu pior caso- a solução tem custo polinomial. e o NP, lá do título? NP é a classe problemas considerados computacionalmente "razoáveis", aqueles para os quais, dada uma possível solução, pode-se testá-la em tempo polinomial. ou seja, para os quais, se conseguirmos uma potencial solução de forma não determinística, temos um algoritmo lá da classe P que diz se a solução é verdeira ou não. talvez venha, daí, o nome da classe: N de "não determinístico" e P de polinomial. para mais detalhes sobre o assunto, de forma tão simples quanto é possível no caso, leia esta explicação do professor paulo feofiloff.
juntando as duas coisas, chegamos ao título do texto de hoje: será que há uma solução polinomial para todos os problemas computacionalmente razoáveis? será que, para cada e todo problema não determinístico polinomial [NP] eu consigo achar uma solução polinomial [em P]? ou seja, será que consigo provar que P=NP, que a classe dos problemas "razoáveis" tem complexidade polinomial, encerrando uma discussão iniciada em 1971 [por cook, veja aqui] e ganhando um prêmio de um milhão de dólares do clay institute? e isso contra a opinião da vasta maioria dos cientistas da área? em pesquisa recente, apenas 9 entre 100 cientistas que estão trabalhando no problema disseram acreditar que P=NP. e apenas 5 entre os 100 disseram que o problema seria resolvido -de uma forma ou de outra- antes de 2010.
se P=NP, haverá conseqüências muito interessantes do ponto de vista de [entre muitas outras áreas] logística, biologia, possivelmente criptografia e, talvez, toda a matemática. porque provar teoremas se tornaria muito mais fácil, segundo o próprio cook, o cientista que começou a discussão: …it [P=NP] would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time… em suma, parte da computação e matemática que está sendo feita e usada hoje pode mudar consideravelmente, com a provável inclusão, na lista, dos sistemas de segurança das transações financeiras. vai ser um auê federal. mundial, aliás.
sim. e daí? o leitor acorda na segunda e, primeira coisa que lê é este blog, com esta conversa mole e complicada sobre obscuridades matemáticas e computacionais quase ininteligíveis… o que é que o autor tá pensando? que isso aqui é aula de teoria da computação? não. este texto está aqui por duas razões. primeira: se P=NP, nossas vidas vão mesmo mudar. pode acreditar. segunda: um brasileiro [e trabalhando no brasil], sóstenes lins, professor titular do departamento de matemática da ufpe, anunciou em seminário recente, em recife, estar finalizando os detalhes de uma prova definitiva de que, sim, P=NP. agora é esperar pra ver os detalhes. boa sorte, sóstenes.
* . * . *
PS1: paulo feofiloff chamou minha atenção para a "lista de woeginger", que tenta acompanhar todas [e até agora malfadadas] tentativas de provar que P é ou não igual a NP. para quem estiver interessado nas definições, debates e tentativas de prova que cercam a controvérsia, é sem dúvida uma boa fonte.
