Por Giuseppe Di Giuseppe Deininger

No ano 2000, o Clay Mathematics Institute (CMI), instituto sem fins lucrativos fundado em 1998 pelo empresário americano Landon Thomas Clay com a intenção de aumentar e disseminar o conhecimento matemático, definiu sete problemas com uma premiação de um milhão de dólares por problema resolvido.

O mais recente deles, o problema P versus NP, foi levantado inicialmente em 1971 por Stephen Cook, cientista da computação e matemático estadunidense-canadense. Nele é perguntado se caso seja fácil verificar que uma possível solução de um problema é verdadeira, também seria fácil resolver o problema.

Como exemplo, o CMI cita a seguinte situação problema: é necessário organizar o alojamento de 400 alunos, sendo que existe espaço para apenas 100 deles nos dormitórios. Além disso, certos estudantes são incompatíveis uns com os outros e por isso é necessário que não fiquem no mesmo dormitório. É fácil perceber que, dada uma possível solução a verificação é rápida, basta checar se os alunos incompatíveis não estão alojados juntos. Porém, achar uma solução do zero é bastante complicado, visto que o número de possíveis combinações de 100 alunos no grupo é maior que o número de átomos existentes no universo conhecido. Assim, é seguro pensar que nenhum computador chegue a ser capaz de solucionar o problema por tentativa e erro.

Desde o início da programação em computadores, a maior parte das primeiras soluções para um problema eram lentas, mas com o tempo novos algoritmos com a capacidade de resolvê-los com maior eficiência eram pensados, porém alguns simplesmente não pareciam ter uma solução rápida o suficiente. Por isso, eles começaram a ser categorizados.

A primeira das categorias, P, representa os algoritmos polinomiais, engloba os problemas que podem ser rapidamente resolvidos por computadores, e o aumento de sua complexidade não vai causar um aumento tão significativo no tempo ou memória gastos pelo computador para solucioná-los. São retratados por um polinômio p(n), que representa o número de passos máximo necessários para a solução dada uma entrada de tamanho n. Nessa categoria se encontram, por exemplo, a multiplicação e ordenamento de termos, seja alfabética ou numericamente.

A segunda categoria, NP, representa os algoritmos não-determinísticos polinomiais, engloba os problemas que, dada uma resposta, é possível checar sua validade em uma quantidade de passos polinomial. Muitos problemas importantes estão inseridos nessa categoria, entre eles o enovelamento de proteínas, cujo entendimento poderia significar a cura de certos tipos de câncer e a decomposição de um número em fatores, método habitualmente utilizado em criptografia.

Stephen Cook conseguiu provar que caso um problema pudesse ser resolvido em tempo polinomial, também seria possível validar uma resposta em tempo polinomial, e por consequência a categoria P está inserida em NP. Alguns problemas inseridos em NP que não eram inicialmente considerados integrantes do grupo P foram desenvolvidos a ponto de sua solução se tornar possível em tempo polinomial. Esses problemas levantaram a pergunta chave do problema P x NP: Será que todos os problemas NP são também P e apenas não tiveram suas soluções polinomiais desenvolvidas, o que significaria que todas elas na verdade seriam P, ou realmente alguns problemas NP são realmente mais difíceis que os P?

Uma outra subcategoria dos NP foi definida quando pesquisadores da área de complexidade computacional perceberam que muitos dos problemas NP eram fundamentalmente o mesmo problema. Esses foram chamados de problemas NP-Completo. Formalmente, um problema L é considerado do tipo NP-Completo se ele cumprir dois requisitos: ser NP e todo problema em NP ser redutível a L em tempo polinomial.

O primeiro problema a ser provado integrante da classe NP-Completo foi o Problema de Satisfatibilidade Booleana que trata de determinar se existe um conjunto de valores para um grupo de variáveis booleanas tal que ele resolva uma dada expressão. Hoje, existem diversos problemas que são comprovadamente pertencentes à categoria NP-Completo, entre eles a solução de quebra-cabeças, Sudoku e os já citados enovelamento de proteínas e fatoração de números.

Os problemas da categoria NP-Completo são fundamentais na questão P x NP, pois a solução de um deles em tempo e espaço polinomiais vai significar que todos os conjuntos P, NP e NP-Completo serão unificados em um grande grupo P. A solução de um problema NP ordinário pode não significar a solução da grande questão porque os problemas nessa classe podem ser apenas membros da classe P cuja solução polinomial simplesmente não era conhecida.

Outra importante categoria é a chamada NP-Difícil. Nelas estão alocados os problemas NP-Completo e os que além de ter o desenvolvimento de uma solução difícil, também possuem a verificação de um candidato ocupando um tempo exponencial. Um dos exemplos mais conhecidos dessa categoria é o jogo de xadrez. É extremamente difícil determinar qual o melhor movimento a ser feito, e ao ser sugerido um possível movimento, também é impraticável verificar se se trata do melhor. É considerado inclusive que é impossível determinar um algoritmo capaz de resolver o problema do jogo de xadrez dada a complexidade de seus cálculos.

Logo, existem duas possíveis soluções para a pergunta de um milhão de dólares. Se P = NP, as categorias P, NP e NP-Completo se tornarão uma única e os dois grandes conjuntos de acordo com o aumento da complexidade se tornarão P e NP-Difícil. Se P ≠ NP, então os grupos continuarão existindo da forma como já são conhecidos.

A grande maioria dos cientistas da computação acredita que P seja de fato diferente de NP. Numa pesquisa realizada com 152 dos maiores teóricos da computação no mundo, 83% disse acreditar que P ≠ NP, 9% considera que P = NP e 8% afirmou não saber ou não considerar os resultados obtidos suficientes para qualquer conclusão. Ainda nessa pesquisa, 53% afirmou acreditar que o problema será solucionado antes de 2100, 41% acredita que ele será resolvido após 2100 e o restante acredita que nunca se chegará a uma prova conclusiva a respeito do tema.

Scott Aaronson, pesquisador de complexidade computacional do Instituto de Tecnologia de Massachusetts afirmou como argumento filosófico para defender que P ≠ NP: “Se P = NP, então o mundo passaria a ser um mundo completamente diferente. Não haveria valor especial em “saltos criativos”, nenhuma diferença fundamental entre resolver um problema e reconhecer sua solução depois de encontrada. Todos que pudessem apreciar uma sinfonia seriam Mozart; todos que pudessem acompanhar uma prova passo a passo seriam Gauss; e todos que pudessem reconhecer uma boa estratégia de investimento seriam Warren Buffett.”. Mais tarde, ele se retratou, visto que estavam ocorrendo várias interpretações que indicariam que ele acreditava que a criatividade humana poderia ser transformada em algoritmos, enquanto que sua intenção era destacar a diferença entre achar ou criar e apenas verificar.

Referências: 

P vs NP Problem. Disponível em: http://www.claymath.org/millennium-problems/p-vs-np-problem. Acesso em: 13 de janeiro de 2018.

The P versus NP Problem. Stephen Cook. Disponível em: http://www.claymath.org/sites/default/files/pvsnp.pdf. Acesso em: 13 de janeiro de 2018.

Explained: P vs. NP. Larry Hardesty. Disponível em: http://news.mit.edu/2009/explainer-pnp. Acesso em: 13 de janeiro de 2018.

P ?= NP Scott Aaronson. Electronic Colloquium on Computational Complexity, 08 de janeiro de 2017.