JOSÉ LUIZ PASTORE MELLO
ESPECIAL PARA A FOLHA

Um número natural é chamado de primo se tem exatamente dois divisores: 1 e ele mesmo. O fascínio que os números primos exercem sobre o homem é quase tão antigo quanto a própria história da matemática. Euclides (325-265 a.C.) demonstrou que existem infinitos números primos.
Eratóstenes (276-194 d.C.), por sua vez, propôs um método para encontrar números primos conhecido como crivo de Eratóstenes. Apesar de ser bastante simples elaborar um programa de computador que use esse método para encontrar números primos até um certo número natural N, o tempo de operação para executá-lo cresceria exponencialmente com o tamanho de N.
Para compreender o que isso significa, imagine um programa de computador cujo tempo de execução seja dado pela exponencial 2N. Executando esse programa para N=1.000 em um computador que realize uma operação a cada milésimo de segundo, a resposta final só seria obtida em 10284 anos, o que é 10274 vezes maior que a idade do universo.
Em geral, problemas cujo tempo de execução é exponencial são de difícil, quando não impossível, tratamento computacional e recebem o nome de problemas NP. Se, por ouro lado, um problema pode ser executado em tempo polinomial com N, ele recebe o nome de problema P e pode ser tratado de forma eficiente por computadores. Por exemplo, se o tempo de execução de um programa fosse dado polinomialmente por N2, encontraríamos sua solução em pouco mais de 16 minutos no computador descrito acima para N=1.000.
Na incansável busca dos cientistas por transformar problemas NP em problemas P, cuja resolução por computador é mais viável, a novidade, divulgada recentemente pela revista "New Scientist", vem da Índia. Três pesquisadores desse país desenvolveram um programa de tempo polinomial para verificar se um número é primo ou não, problema até então considerado como NP. Ainda não se sabe ao certo o impacto da demonstração, mas o fato é que, mais uma vez, os indianos demonstram ao mundo a força e a tradição de sua pesquisa na área de computação e matemática.