Para quem é da área da computação há um problema que há muito tempo vem sendo estudado e até o momento ainda não encontraram solução definitiva. O problema P vs NP.
Na computação existe uma infinidade de problemas matemáticos que nunca terão solução (como o problema do detector de loops infinitos), no entanto existem outros problemas que os computadores conseguem resolver, mas para isso precisam de tanto tempo computacional que praticamente se tornam irresolúveis.
Especificamente para este texto estamos falando do problema de tentar responder se existem problemas matemáticos cuja resposta pode ser verificada em tempo polinomial, que não possam ser resolvidos em tempo polinomial. Ou seja, existem problemas complexos que podem ser verificados facilmente, mas quando tentamos encontrar uma solução, sem informações parciais prévias, a resposta se torna muito difícil de encontrar.
Por exemplo: se eu lhe disser que o número 13.717.421 pode ser escrito como o produto de dois outros números primos, você provavelmente demorará para provar isso; contudo, se eu lhe disser que ele é o produto de 3.607 por 3.803, você seria capaz de muito rapidamente verificar isso.
Então, vamos entender o que de fato são problemas P e NP.
P e NP são classes de problemas. Os referidos como pertencentes a classe P são resolvidos pelos computadores em tempo razoável e são chamados de problemas polinomiais, a letra P vem deterministicamente de Polinomiais. Esses problemas são chamados assim, porque o tempo para calcular uma resposta pode ser descrito por uma função polinomial no tamanho dos dados de entrada. (No caso do problema da fatoração, por exemplo, o tamanho de uma instância é o número de dígitos de N, ou seja, cerca de logN).
Em outras palavras, o algoritmo é polinomial se existe um número i (o mesmo para todas as instâncias) tal que o consumo de tempo do algoritmo é Ο(Ni ), sendo N o tamanho da instância.
Algoritmos polinomiais são considerados rápidos – ainda que seja difícil aceitar como rápido um algoritmo que consome tempo proporcional a N500, por exemplo.
Algoritmos não polinomiais — como, por exemplo, os que consomem tempo proporcional a 2N ou a 1.1N — são considerados inaceitavelmente lentos (ainda que possam ser úteis para valores muito modestos de N)
Já a classe NP consiste em todos os problemas de decisão cujas soluções positivas podem ser verificadas em tempo polinomial dada a informação correta, ou de forma análoga, cujas soluções podem ser encontradas em tempo polinomial em uma máquina não determinística. NP vem de Não deterministicamente Polinomiais.
Isso quer dizer que é fácil verificar se uma resposta para um problema é verdadeira quando se está diante de uma. Mas quando queremos gerar uma resposta para tal problema, a computação se torna muito difícil. E somente em um computador com paralelismo total (não determinístico) podemos encontrar as respostas.
O problema de encontrar os dois números primos que quando multiplicados geram 13.717.421 é de fácil verificação quando termos a resposta, no caso 3.607 e 3.803. Portanto a verificação é feita em tempo polinomial no número de dígitos do número gerado pela multiplicação dos termos, de forma costumeira.
Sendo assim, temos mais uma definição para os problemas da Classe NP. Todos os problemas da classe P estão na classe NP. Pois também são verificáveis em tempo polinomial.
Existem problemas que são considerados os mais difíceis de NP, os NP-Difíceis. Essa classe constitui problemas que não precisam estar em NP. Ou seja, eles não precisam ser verificados em tempo polinomial. Mas qualquer problema NP pode ser reduzido para um problema NP-Difícil.
A redução de um problema a outro acontece comumente em nossas vidas, por exemplo, quando você sai com seus amigos e quer dividir uma conta entre todos. O que você fará é pegar o total da nota e dividir pelo número de pessoas e esse resultado é o quanto cada um contribuirá. Do mesmo modo você pode subtrair um valor igual da conta para cada pessoa. Então o seu problema de divisão foi reduzido a um problema de subtração.
De maneira semelhante aconteceria se você marcasse uma festa com seus amigos e combinasse de cada um levar duas cervejas, a quantidade final de cervejas seria duas vezes a quantidade de pessoas presentes (que levaram, certo?). Você também pode somar duas cervejas por cada pessoa que levou. Nesse caso o problema de multiplicação foi reduzido a um problema de soma.
E isso é bastante comum na computação, se você não souber como dividir poderia trabalhar com subtração no lugar, assim como com a multiplicação, que poderia ser substituída pela soma. Se temos um problema e não sabemos como solucioná-lo, podemos tentar reduzir a um caso de outro que sabemos.
Voltando ao assunto principal, se um problema pertencer a classe NP-Difícil e ao mesmo tempo pertencer a classe NP, ele entra na classe NP-Completo. Isso quer dizer que qualquer problema NP poderá ser reduzido para este problema (qualquer problema NP não é mais difícil do que ele) se ele puder ser verificado em tempo polinomial.
Essa classe de problemas NP-Completos é muito importante para a computação, e existem problemas que são ditos como pertencentes a classe NP-Completa. Se um problema NP-Completo for solucionado em tempo polinomial quer dizer que qualquer problema NP também poderá e com isso temos P=NP.
Isso deu início a pergunta de 1 Milhão de Dólares, “P = NP?”. Mas ainda não se sabe se isso é verdadeiro. Até o momento da produção deste texto (03/04/2019) não temos uma resposta satisfatória.
Diversos trabalhos atacam esta questão, tentando responde-la, como você pode verificar na referência [2]. Mas até o momento nenhuma resposta foi aceita pela comunidade.
Na referência [5] podemos encontrar uma lista de problemas pertencentes a classe NP-Completa. Outros exemplos de problemas podem ser encontrados aqui no deviante nesse meu texto antigo, no texto de Felipe Augusto e temos até mesmo um método para solucionar alguns desses problemas. E quem conseguir soluciona-los em tempo P conseguirá o grande prêmio e mudará a computação para sempre.
Uma grande esperança para diminuir esse tempo computacional está por vir com a computação quântica e seus qubits. Estamos acompanhando essa competição que já dura 40 anos.
Referências:
[1] Complexidade: problemas NP-completos
[3] The Status of the P Versus NP Problem
[4] P versus NP
