P vs. NP: O problema de um milhão de dólares

No início do século, o Clay Mathematics Institute lançou o chamado Millennium Prize Problems: sete problemas matemáticos de grande complexidade e importância, cuja resolução traria grandes desenvolvimentos e avanços tecnológicos. Para incentivar as mentes brilhantes a resolver esses problemas, foi oferecido o prêmio de um milhão de dólares. Dentre os diversos problemas listados, um deles é de extrema importância no mundo da otimização: se P é igual a NP. 

Vamos dar um passo atrás para entender melhor o que essas letras e esta equação representam. Para isso, podemos definir duas classes de problemas. A classe P (Tempo polinomial determinístico), composta por problemas que podem ser resolvidos rapidamente, e a dificuldade cresce lentamente com a dimensão do problema. E a classe NP (Tempo polinomial não determinístico), cujas soluções podem ser verificadas rapidamente. Portanto, a questão é se todo problema em que a solução pode ser verificada rapidamente também pode ser resolvido rapidamente.

Esta pergunta permanece sem resposta devido ao fato de ainda não ter sido provado que existem problemas nos quais a solução pode ser verificada rapidamente, mas que a descoberta de uma solução não pode ser determinada de forma eficiente. 

Suponha que você queira viajar pelo Brasil e visitar todas as 26 capitais dos estados e o  Distrito Federal. Ao preparar o roteiro, você se pergunta: é possível realizar esta viagem percorrendo menos de 15 mil km? A resposta para esta pergunta é extremamente difícil, já que seria necessário testar todas as ordens possíveis de trajeto e calcular a sua distância. No entanto, é muito fácil verificar se um roteiro pronto pode ser percorrido com menos de 15 km, já que basta somar a distância entre as cidades na ordem definida. Este problema é, portanto, NP, dado que uma solução pode ser rapidamente verificada, mas ainda não se sabe se é também P, pois ainda não foram encontrados métodos de resolução em tempo polinomial (extremamente rápidos).

Uma terceira e importante classe de problemas é chamada de NP-completo: são problemas NP que podem ser transformados uns nos outros em tempo polinomial. Por exemplo, o problema de encontrar a melhor rota a ser percorrida pode ser transformado em uma problema de definição de carregamento de materiais com determinado valor em um contêiner de capacidade limitada como o  problema da mochila.

Conhecendo essas classes de problemas, e os tipos de problemas que representam, podemos ter uma ideia das consequências que a resolução desta questão pode trazer. Ao se provar que P é igual à NP, provavelmente algoritmos para resolver um problema complexo como o da melhor rota para conhecer todas as capitais brasileiras seria desenvolvido. Ao se resolver este problema, e, conhecendo a características dos problemas NP-completos, uma infinidade de outros problemas extremamente complexos também seriam resolvidos, passando pela resolução de problemas industriais clássicos e possibilitando desde a descoberta de novos remédios para doenças como câncer à predição da estrutura de proteínas. Haveriam também consequências graves, como sistemas de criptografia quebrados, já que as suas resoluções se tornariam fáceis.

Provar o contrário, que P é diferente de NP, também traria grandes benefícios: permitiria uma melhor orientação em pesquisas futuras e um direcionamento na teoria de complexidade computacional. Por exemplo, poderiam se intensificar pesquisas em heurísticas e meta-heurísticas, que buscam encontrar soluções boas, mas não necessariamente garantem a otimização.

Portanto, o mundo como conhecemos hoje seria muito impactado por qualquer resposta a este grande problema. Se você acha que sabe responder se P = NP, não perca tempo, pois o clube dos milionários te espera!

Autor: Cassiano Lima - Consultor Senior na Cassotis Consulting

  Coautor: Fabio Silva - Gerente Sênior na Cassotis Consulting