Cópia pirata de artigo da Folha.com, 10/8/2010
DA NEW SCIENTIST
Será que a maior questão em ciência da computação foi respondida?
No dia 6 de agosto, Vinay Deolalikar,
um matemático nos laboratórios da Hewlett-Packard, em Palo Alto, Califórnia,
distribuiu cópias de um artigo preliminar intitulado P =/= NP
.
Essa afirmação concisa poderia ter consequências profundas para a habilidade de resolver vários tipos de problemas computacionais.
Ela também responde um dos sete problemas que concorrem ao Millennium Prize, prêmio oferecido pelo Instituto Clay de Matemática. Se Deolalikar estiver correto, ele ganhará US$ 1 milhão (R$ 1,74 milhão).
A questão P vs. NP
refere-se a velocidade
na qual um computador pode realizar uma tarefa como a fatoração de um número.
Nessa tarefa, importante em criptografia,
o objetivo é encontrar o conjunto de números primos que,
multiplicados, produzem esse mesmo número.
Se o resultado for dado (isto é, os números primos), é rápido checar se sua multiplicação leva ao número original. O problema é encontrar um método capaz de encontrar esse fatores que não envolva simplesmente tentativa e erro.
Algumas tarefas podem ser completadas rapidamente. Essas tarefas fazem parte da classe P, pois seu tempo de resolução é proporcional a uma função polinomial do tamanho do input (por exemplo, o tempo para multiplicar números cresce proporcionalmente com o número de multiplicações envolvidas).
Se a resposta da tarefa pode ser checada rapidamente, mas não resolvida rapidamente, ela pertence à classe NP (por exemplo, o tempo para checar se os fatores produzem o número desejado é um processo rápido; descobrir quais são esses fatores, não).
Se P = NP, todo problema que pode ser checado rapidamente também poderia, em princípio, ser resolvido rapidamente. O resultado teria grandes consequências para a segurança na internet. A dificuldade de fatorar números muito grandes é o principal método empregado para proteger dados na rede mundial.
O resultado de Deolalikar mostra o contrário. Seu argumento gira em torno de uma tarefa particular, o problema de satisfazibilidade booleana (SAT). O problema consiste em verificar se uma coleção de asserções lógicas podem ser todas simultaneamente verdadeiras. Esse problema é NP.
Segundo Deolalikar não existe um programa que possa completar o SAT a partir do zero, sem que envolva tentativa e erro. Seu argumento envolve física estatística, fazendo uso da estrutura matemática que emerge do uso das mesmas regras físicas por um sistema aleatório.
Se o resultado sobreviver ao escrutínio dos pares, ele provaria que as duas classes de problemas, P e NP, não são idênticos. Isso imporia limites severos nos tipos de atividades que computadores poderiam realizar. Uma implicação importante é que muitas tarefas podem ser complexas de maneira irredutível.
Para alguns problemas, incluindo fatoração, o resultado não diz claramente se ele poderá ser resolvido rapidamente. Mas uma sub-classe enorme de problemas, conhecidos como NP-completos, estão fadados.
Um exemplo famoso é o do caixeiro-viajante. O problema envolve descobrir a menor rota para percorrer um conjunto de cidades. Dada uma rota, é possível checar rapidamente se ela é melhor ou pior que outra rota. Mas, como P =/= NP, não haveria nenhum programa capaz de completar a tarefa a partir do zero.
O problema do caixeiro-viajante é enfrentado rotineiramente pela indústria. Na fabricação de chips, por exemplo, as empresas buscam encontrar uma rotina que minimize o número de movimentos de um braço robótico, a fim de economizar tempo e energia.
Teóricos de complexidade receberam bem a primeira versão do artigo de Dolalikar. Mas, quando a versão final for divulgada na semana que vem, o processo de avaliação deverá ser intensificado.