P = NP (ou não...)
Tô começando a achar que está na moda falar de Teoria da Computação. Um dos problemas mais famosos da Ciência da Computação e da Matemática (senão o mais famoso) apareceu nesta quarta-feira no New York Times. Além disso, esse problema também é um dos problemas do milênio, e quem conseguir resolvê-lo leva US$1.000.000 para casa. Que problema é esse? É o problema de P vs. NP.
A questão é saber se o conjunto dos problemas que podem ter suas respostas verificadas rapidamente (NP) é igual ao conjunto dos problemas que podem ser resolvidos rapidamente (P). Um problema clássico que está em NP é o “15 puzzle”.
Se você teve infância, você já brincou alguma vez com esse quebra-cabeça; mas se não teve, eu explico como funciona… O quebra-cabeça vem de fábrica igual na figura acima, totalmente embaralhado. O seu objetivo é o mais simples do mundo: colocar os números em ordem, mas sem usar o “jeitinho brasileiro” e arrancar as peças do tabuleiro ☺
Mas por que o “Fifteen Puzzle” pertence à NP? Pois se alguém disser uma seqüência de movimentos, é ** fácil verificar** se ela está certa. Ora bolas, é só fazer os movimentos e ver se no final os números estão em ordem! Já para encontrar uma seqüência de movimentos o problema fica enorme… Você pode tentar escrever um programa de computador para resolver o Fifteen Puzzle, afinal os computadores são máquinas incrivelmente poderosas, não é mesmo? Só que até hoje, nenhuma das mentes mais brilhantes do mundo encontrou uma solução mais inteligente do que a FORÇA BRUTA, ou seja, tentar todas as combinações possíveis.
À primeira vista parece que o Fifteen Puzzle é impossível de ser resolvido de maneira mais rápida, e assim PARECE que ele não pertence ao conjunto P. Outros dois jogos bem famosos, que também têm essa característica são o Campo Minado e o Sudoku. Tente pensar um pouco agora sobre como é tão fácil chechar uma reposta de Sudoku, mas tão difícil de resolver um jogo…
O fato de que até hoje não se encontrou nenhuma solução “rápida” para esses problemas nos faz crer que P é diferente de NP, ou seja, existem problemas que são fáceis de checar, mas difíceis de resolver. O fato é que não há uma prova matemática dessa desigualdade. No fim das contas, essa nossa incapacidade de inventar uma boa solução para tais problemas pode ser apenas falta de inteligência e criatividade.
Se até agora você está achando que tudo isso de P, NP, quebra-cabeças e campo minado não tem nada a ver com a “vida real”, está na hora de mudar seus conceitos. Um dos problemas mais famosos que pertencem a NP é estudado pelos biólogos, e é o dobramento de proteínas.
Esse problema consiste em, a partir da estrutura geométrica tridimensional de uma proteína, descobrir qual é a seqüência de aminoácidos que a compôem. Médicos e bioquímicos no mundo inteiro já sabem que o acúmulo de proteínas mal-dobradas é a principal causa de várias doenças, então uma melhor compreensão de como funciona esse processo pode ajudar e muito a saúde da humanidade.
Ainda quero escrever um outro post para falar um pouco mais sobre esse assunto, mas por enquanto, pense duas vezes quando for xingar um nerd de egoísta. Você pensa que ele está escrevendo um programa para resolver Sudoku, mas na verdade ele pode estar ajudando a cura do câncer :P