P versus NP: o problema de US$ 1 milhão que pode decidir os limites da criatividade computacional

Existe uma pergunta, formulada em linguagem técnica de ciência da computação, que segue sem resposta há mais de cinquenta anos e que, se respondida de um certo jeito, derrubaria de uma vez boa parte da infraestrutura digital que sustenta bancos, mensagens criptografadas e sistemas de senha em todo o planeta. Essa pergunta é conhecida pelo nome curto de “P versus NP”, e ela está na lista dos sete Problemas do Milênio selecionados pelo Clay Mathematics Institute em 2000 — cada um deles com um prêmio de US$ 1 milhão para quem apresentar uma solução aceita pela comunidade matemática. Até hoje, apenas um dos sete foi resolvido: a Conjectura de Poincaré, provada por Grigori Perelman, que recusou o prêmio.

P versus NP costuma ser descrito como um problema “abstrato”, territorial de matemáticos e cientistas da computação teórica. Essa descrição é enganosa. A pergunta central — existe alguma maneira eficiente de resolver um problema sempre que é fácil conferir se uma resposta dada está certa? — toca diretamente em coisas muito concretas: a segurança da criptografia que protege compras on-line e comunicações bancárias, a possibilidade de calcular rapidamente a forma como uma proteína se dobra no espaço, e os limites teóricos de qualquer sistema, humano ou artificial, capaz de “encontrar” soluções criativas em vez de apenas testá-las uma a uma.

A maioria absoluta dos especialistas acredita que a resposta é não — que P é diferente de NP, e que existe uma barreira real e permanente entre resolver um problema e apenas verificar uma solução para ele. Mas “acreditar” não é a mesma coisa que “provar”, e ninguém, até agora, conseguiu provar coisa nenhuma em nenhuma das duas direções.

O que P e NP realmente significam

Em ciência da computação teórica, a letra P representa a classe dos problemas que podem ser resolvidos por um computador em “tempo polinomial” — ou seja, o tempo necessário para resolvê-los cresce de forma razoavelmente controlada conforme o problema aumenta de tamanho, sem explodir descontroladamente. Ordenar uma lista de números, buscar um nome em um cadastro, calcular a rota mais curta entre dois pontos em um mapa simples: todos esses são problemas de classe P, resolvidos por algoritmos eficientes que já existem há décadas.

A letra NP representa outra coisa: a classe dos problemas cuja solução, uma vez apresentada, pode ser verificada rapidamente, em tempo polinomial — mesmo que ninguém saiba como encontrar essa solução de forma igualmente rápida. O exemplo clássico é o quebra-cabeça de Sudoku em tabuleiros muito grandes: preencher um Sudoku gigante do zero pode ser extremamente trabalhoso, mas, se alguém entrega um tabuleiro já preenchido, checar se ele está correto é trivial e rápido. Outro exemplo é o problema do caminho hamiltoniano — decidir se existe uma rota que passa por cada cidade de um mapa exatamente uma vez. Encontrar essa rota pode ser terrivelmente difícil à medida que o número de cidades cresce, mas, dado um trajeto pronto, verificar se ele cumpre a regra é rápido.

Todo problema de classe P também está automaticamente em NP — se dá para resolver rápido, dá para verificar rápido, bastando resolver de novo. A pergunta em aberto é a direção contrária: será que todo problema cuja solução é fácil de verificar também é, secretamente, fácil de resolver — só que ninguém ainda descobriu como? Essa é, em essência, a pergunta “P = NP?”.

O Teorema de Cook-Levin e o nascimento da NP-completude

O salto que transformou essa pergunta filosófica em um programa de pesquisa matemático rigoroso veio em 1971, com um artigo do cientista da computação canadense-americano Stephen A. Cook, “The Complexity of Theorem-Proving Procedures”, apresentado no Terceiro Simpósio Anual de Teoria da Computação da ACM (STOC). Cook mostrou que existe um problema específico — o problema da satisfatibilidade booleana, ou SAT, que pergunta se é possível atribuir valores verdadeiro/falso a variáveis lógicas de modo a tornar verdadeira uma fórmula inteira — para o qual qualquer outro problema de NP pode ser “traduzido” ou “reduzido” em tempo polinomial. Isso quer dizer que, se alguém encontrasse um algoritmo rápido para resolver SAT, esse mesmo algoritmo poderia ser adaptado para resolver rapidamente qualquer problema da classe NP. O matemático soviético Leonid Levin chegou, de forma independente e quase simultânea, a um resultado equivalente — por isso o resultado é hoje chamado de Teorema de Cook-Levin.

Um problema com essa propriedade — de que todos os outros problemas de NP podem ser reduzidos a ele em tempo polinomial — é chamado de “NP-completo”. A ideia central é poderosa: em vez de perguntar, um por um, se cada problema difícil individual tem solução rápida, basta descobrir se um único problema NP-completo tem solução rápida. Se tiver, todos os problemas de NP também terão — e P seria igual a NP. Se alguém provar, ao contrário, que nenhum algoritmo rápido pode existir para um problema NP-completo, isso derrubaria a possibilidade de solução rápida para todos os outros ao mesmo tempo.

A lista de Karp e a onipresença de problemas NP-completos no mundo real

Um ano depois, em 1972, o cientista da computação Richard M. Karp publicou o artigo “Reducibility Among Combinatorial Problems”, no qual demonstrou que 21 problemas combinatórios clássicos e amplamente estudados — muitos deles com aplicações industriais diretas — eram todos NP-completos, reduzindo-os entre si e ao SAT de Cook e Levin. A lista de Karp incluía, entre outros, o problema do caixeiro-viajante (encontrar a rota mais curta que visita um conjunto de cidades e retorna ao ponto de partida), o problema da cobertura de vértices em grafos, o problema da mochila (escolher itens de valor e peso variados para maximizar valor sem exceder uma capacidade) e o problema de coloração de grafos.

O impacto prático desse artigo foi enorme: de repente, ficou claro que problemas de otimização logística, escalonamento de tarefas, roteamento de redes e alocação de recursos — problemas que empresas de transporte, telecomunicações e manufatura enfrentam todos os dias — pertenciam, todos, à mesma família de dificuldade fundamental. Não se tratava de problemas isolados e mal compreendidos; eram instâncias de uma barreira computacional compartilhada. Desde então, a lista de problemas conhecidos como NP-completos cresceu para milhares, cobrindo áreas que vão de bioinformática a inteligência artificial, incluindo formulações simplificadas do problema de prever como uma proteína se dobra no espaço tridimensional a partir de sua sequência de aminoácidos.

Por que quase todo mundo acredita que P ≠ NP — mas ninguém provou

Se a maioria dos especialistas está convencida de que P é diferente de NP, por que a prova continua fora de alcance? Uma parte da resposta está em décadas de tentativas frustradas usando as ferramentas mais óbvias. Em 1975, os cientistas da computação Theodore Baker, John Gill e Robert Solovay mostraram que técnicas de prova baseadas em “relativização” — uma classe inteira de argumentos que os pesquisadores vinham usando — não seriam capazes, por si só, de resolver a questão em nenhuma das duas direções, porque existem versões modificadas do problema em que a relativização produz respostas opostas. Décadas depois, em 1994, Alexander Razborov e Steven Rudich identificaram outra barreira, batizada de “provas naturais”, mostrando que uma ampla categoria de estratégias de prova combinatória também esbarra em limitações estruturais profundas, ligadas até a suposições da própria criptografia.

O físico e cientista da computação Lance Fortnow resumiu esse quadro de forma influente em seu artigo de 2009 “The Status of the P versus NP Problem”, publicado na revista Communications of the ACM (volume 52, número 9): a intuição da maioria dos pesquisadores aponta fortemente para P ≠ NP, mas as ferramentas matemáticas atualmente disponíveis não parecem suficientes para fechar essa distância. O problema atrai, todos os anos, alegações de solução — a maioria delas nunca chega a ser publicada em periódico revisado por pares, e nenhuma resistiu ao escrutínio da comunidade até hoje.

O que mudaria, de fato, se P fosse igual a NP

A resposta popular costuma exagerar um pouco: uma prova de que P = NP não quebraria automaticamente toda a criptografia do planeta amanhã de manhã, porque a prova poderia ser puramente teórica, sem indicar um algoritmo prático e rápido o suficiente para uso real — a diferença entre “existe” e “dá para construir e rodar” é enorme na prática da ciência da computação. Dito isso, uma prova construtiva, que realmente entregasse um algoritmo eficiente para um problema NP-completo, teria consequências dramáticas. Boa parte da criptografia de chave pública usada hoje — a que protege transações bancárias, mensagens privadas e certificados de segurança na internet — depende da suposição de que certos problemas matemáticos são difíceis de resolver mas fáceis de verificar quando a resposta certa é conhecida; um colapso de P e NP retiraria o alicerce teórico dessa suposição, obrigando a uma reconstrução completa dos sistemas de segurança digital. Na biologia computacional, formulações simplificadas do problema de dobramento de proteínas já foram formalmente demonstradas como NP-completas, o que significa que um algoritmo rápido genérico para problemas NP-completos aceleraria, em princípio, a previsão da estrutura tridimensional de proteínas a partir de sua sequência — um problema central para o desenho de medicamentos. E toda a vasta família de problemas de otimização logística listada por Karp — roteamento de frotas, escalonamento de produção, alocação de recursos em redes — passaria a admitir soluções ótimas exatas em tempo viável, em vez de depender, como hoje, de aproximações e heurísticas.

Meio século de resistência, e nenhum fim à vista

Desde o artigo de Cook em 1971, o problema resistiu a mais de cinco décadas de tentativas por parte de alguns dos matemáticos e cientistas da computação mais capazes do mundo, sem que nenhuma prova tenha se sustentado. O cientista da computação Scott Aaronson, em seu levantamento técnico “P ?= NP”, publicado no volume coletivo Open Problems in Mathematics (Springer, 2016), descreve o estado da arte como um campo onde os obstáculos conhecidos — relativização, provas naturais e, mais recentemente, “algebrização” — não provam que uma solução seja impossível, mas indicam que ela exigirá ideias matemáticas genuinamente novas, ainda não inventadas. Não há, hoje, nenhum sinal concreto de que essa prova esteja próxima.

O que resta, enquanto isso, é um problema que segue organizando boa parte da ciência da computação teórica ao redor de uma única pergunta simples de enunciar e extraordinariamente difícil de responder. Cada novo algoritmo eficiente descoberto para um caso particular de problema difícil, cada nova barreira teórica identificada, é lido pela comunidade como mais uma peça de um quebra-cabeça que, até agora, se recusa a fechar — em qualquer uma das duas direções.

Fontes citadas neste artigo: