Thomas Malthus argumentou, num ensaio publicado no final do século XVIII, que o desenvolvimento económico das classes mais desfavorecidas nunca iria acontecer porque qualquer melhoria que fosse possível na produção de bens e alimentos seria imediatamente compensada por um aumento da população que iria consumir esses bens. A armadilha de Malthus, como ficou conhecida esta teoria, é uma consequência de a população se multiplicar geometricamente mas os meios de produção apenas poderem crescer aritmeticamente. Curiosamente, esta diferença entre um crescimento aritmético e um crescimento geométrico está também na base de um dos mais importantes problemas científicos em aberto.

Thomas Malthus argumentou, num ensaio publicado no final do século XVIII, que o desenvolvimento económico das classes mais desfavorecidas nunca iria acontecer porque qualquer melhoria que fosse possível na produção de bens e alimentos seria imediatamente compensada por um aumento da população que iria consumir esses bens. A armadilha de Malthus, como ficou conhecida esta teoria, é uma consequência de a população se multiplicar geometricamente mas os meios de produção apenas poderem crescer aritmeticamente. Curiosamente, esta diferença entre um crescimento aritmético e um crescimento geométrico está também na base de um dos mais importantes problemas científicos em aberto.

Para perceber a diferença, imagine o leitor que entra no seu carro e acelera a fundo. Ao fim de cerca de oito segundos (se o leitor tiver um carro razoável, mas não um Ferrari) atinge cerca de 100Km/h e percorreu cerca de 100 metros. Imagine agora que o seu carro é muito especial e pode continuar a acelerar dessa forma para sempre. Em menos de um minuto e meio já vai à velocidade de um avião a jacto, tendo percorrido cerca de 14Km. Em quatro horas passa pela Lua mas, mesmo assim, demorará cerca de cinco anos a atingir a estrela mais próxima fora do nosso sistema solar, Proxima Centauri (se não estiver sujeito a efeitos relativísticos). A velocidade do seu carro cresce de acordo com uma progressão aritmética do tempo e o espaço percorrido cresce de acordo com uma potência (o quadrado) do mesmo.

Imagine agora o leitor uma outra experiência, também esta puramente conceptual. Pegue nesta folha de jornal e dobre-a ao meio, ficando com duas folhas sobrepostas, com o dobro da espessura. Imagine que continua a dobrar o resultado ao meio, fazendo uma dobra a cada segundo. Em apenas dez segundos, a espessura do resultado é semelhante à de uma lista telefónica (para os leitores mais jovens que não sabem o que é uma lista telefónica, imaginem um livro com cerca de 5cm de espessura). Continuem a dobrar e, em 20 segundos, a espessura total é da altura de um prédio de 15 andares. Aos 45 segundos a pilha de papel vai até à Lua e, em menos de 70 segundos, atinge Proxima Centauri.

Estas duas experiências ilustram a diferença entre um crescimento aritmético e um crescimento geométrico. Os matemáticos e os informáticos conhecem muito bem a diferença entre estes dois tipos de crescimento, e sabem que o crescimento geométrico acaba sempre por ser mais rápido, muito mais rápido, que o crescimento aritmético, ou mesmo que qualquer potência do crescimento aritmético (o quadrado, por exemplo).

Mas, dirá o leitor, estão muito bem essas curiosidades matemáticas, mas que têm elas a ver com o milhão de dólares? Paciência, caro leitor, tem tudo a ver. Acontece que um dos mais importantes problemas científicos em aberto consiste exactamente em determinar quais os problemas que se podem resolver eficientemente (isto é, em tempo que cresce apenas aritmeticamente com a dimensão do problema) e quais os problemas que não se podem resolver eficientemente (aqueles que exigem um tempo que cresce geometricamente com a dimensão do problema).

Imagine que lhe dou um mapa da Europa, com as 44 capitais assinaladas, e lhe pergunto se existem duas capitais europeias que distem mais de 4500Km? Para um computador, ou mesmo para o leitor, é fácil responder a esta pergunta, simplesmente analisando todos os pares de capitais (são “só” 946 pares) e calculando a respectiva distância, com recurso a uma tabela ou a um mapa.

Mas suponha agora que a pergunta é: será possível visitar todas as 44 capitais europeias percorrendo menos de 20.000Km? É muito difícil responder a esta pergunta porque, basicamente, há que experimentar todas as ordens possíveis pelas quais se poderiam visitar estas capitais e calcular o comprimento total desse trajecto. Acontece que o número de ordens possíveis é muito, muito maior, que o número de folhas de jornal na pilha que o leitor obteve na experiência no princípio deste artigo. Curiosamente, é porém muito fácil verificar uma resposta positiva para esta pergunta. Basta que lhe seja dada uma ordem pela qual as cidades deverão ser visitadas, e com base nessa ordem, calcular a distância total somando cada um dos trajectos entre cidades. A dificuldade advém exactamente do facto de não se saber qual é a melhor ordem, o que leva à necessidade de experimentar todas as ordens possíveis.

Em computação, chama-se P ao conjunto dos problemas deste tipo cuja solução pode ser determinada eficientemente, em tempo que cresce lentamente com a dimensão do problema (aritmeticamente, ou com potências desta dimensão). Chama-se NP ao conjunto dos problemas deste tipo cuja solução pode ser verificada eficientemente. Obviamente, podem existir problemas sujas soluções podem ser verificadas de forma eficiente, mas que demoram muito tempo a ser determinadas. O jogo do Sudoku é um exemplo de um desses problemas, tal como o problema de achar o caminho mais curto que permite visitar um certo número de cidades. Sabe-se que alguns problemas em NP (como o Sudoku) tem uma característica especial: se for encontrada uma solução eficiente para um deles (qualquer um), então essa solução poderá ser adaptada para resolver eficientemente qualquer outro problema em NP. Chamam-se a estes problemas NP-completos, e existem centenas deles.

Acontece que nunca ninguém conseguiu provar que existe um problema cuja solução possa ser verificada de forma eficiente, mas que não possa ser determinada de forma eficiente. Um problema assim pertenceria a NP mas não pertenceria a P. Se nenhum destes problemas existir, então P = NP, ou seja, os dois conjuntos de problemas são exactamente iguais. Se algum destes problemas existir, então P ≠ NP, e existem problemas para os quais é muito difícil achar soluções que são, porém, fáceis de verificar. Por outro lado, para provar que P é igual a NP, bastaria achar uma solução eficiente para um problema NP-completo (por exemplo, o Sudoku). Essa solução poderá ser adaptada para resolver eficientemente qualquer problema em NP.

Determinar se P é ou não igual a NP é um dos mais importantes problemas em matemática e em computação, e é um dos sete problemas do milénio, definidos pelo Clay Institute, que oferece um prémio de um milhão de dólares pela solução de qualquer um deles. Destes sete problemas, apenas um (a chamada conjectura de Poincaré) foi resolvido até à data. A solução deve-se a Grigori Perelman, um matemático russo, vencedor da medalha Fields (considerado por muitos o prémio Nobel da matemática) que, após encontrar a solução, decidiu não reclamar o prémio.

Qualquer pessoa que consiga provar que P é igual a NP, ou que P é diferente de NP, ganhará este prémio. Mas, ao contrário de outros problemas que constam nesta lista do Clay Institute, a resolução deste problema poderá ter enormes consequências práticas. Sabemos que, se P for igual a NP, então será possível criar programas que resolver complexos problemas eficientemente, como por exemplo achar novas drogas para combater o cancro ou criar sistemas com inteligência artificial. Em compensação, a privacidade na Internet tornar-se-á muito mais difícil, porque todos os sistemas actualmente utilizados para cifrar mensagens se tornarão vulneráveis.

Por outro lado, se P for diferente de NP, alguns problemas ficarão para sempre fora do alcance dos computadores, mesmo dos supercomputadores do futuro ou dos tão falados computadores quânticos. Muitas questões da área da inteligência artificial, da biologia e de muitos outros domínios serão muito mais difíceis, ou mesmo impossíveis, de resolver e não teremos, nunca, a resposta para algumas perguntas que é possível formular.

Embora nunca ninguém tenha identificado um problema que esteja em NP e não em P, a maior parte dos cientistas acredita que P é diferente de NP. É provável que não existam ainda as ferramentas matemáticas necessárias para resolver este problema e poderá levar um século ou mais a criá-las. Poderá mesmo acontecer que este problema nunca seja resolvido. Num mundo onde tudo acontece tão rapidamente, é interessante saber que há questões matemáticas profundas e com grande impacto na sociedade, que continuam em aberto e a desafiar a inteligência humana.