Antes de abordar o tema P vs NP, vamos à definição do que séria p e np. Problemas em que levam pouco tempo para serem resolvidos, problemas “fáceis”, são problemas que podem ser resolvidos por algoritmos polinomiais, onde os classificamos na classe de problemas polinomiais(P). Exemplos desses algoritmos:
– Algoritmos com pesquisa binária (complexidade O(log n)).
– Pesquisa sequencial (complexidade O(n)).
– Ordenação por isenção (complexidade O(n²)).
– Multiplicação de matrizes (complexidade O(n³)).
Então os algoritmos polinomiais sempre tem sua complexidade na função de complexidade:
– O(p(n)), onde p(n) é um polinômio.
Por outro lado, temos problemas em que sua solução requer muito tempo e recursos computacionais, chamados de problemas de tempo polinomial não determinístico(NP). Exemplos desses problemas:
– Subconjunto de um conjunto (complexidade O(2^n)).
– Problema do caixeiro viajante (complexidade O(n!)).
Para esses problemas temos sua complexidade em função de:
– O(), c > 1.
A imagem abaixo temos a relação entre essas classes de problemas:
Trivialmente P é um subconjunto de NP, embora ainda não seja provado, muitos especialistas acreditam que P é um subconjunto próprio de NP.
O problema “P versus NP” é o principal problema aberto da Ciência da Computação. Possui também enorme relevância em campos que vão desde a Engenharia até a criptografia aplicada aos serviços militares e às transações comerciais e financeiras via Internet.
Se a resposta for P≠NP, as coisas ficariam mais ou menos na mesma, mas se for P=NP, estão muitas coisas mudariam.
Para resolver algoritmos da classe NP usamos alternativas á força bruta, como solução gulosa ou programação dinâmica. Toda nossa criptografia atual, com exceção da computação quântica, é baseada em P≠NP, ou seja, para quebrar a criptografia seria muito difícil, uma vez que não temos algoritmos tão eficientes. Mas caso P=NP temos então algoritmos Polinomiais para problemas NP, então poderíamos resolver, em pouco tempo, problemas como do caixeiro viajante, para os quais hoje temos algoritmos muito trabalhosos, isso seria benéfico para a indústria, as comunicações e o desenvolvimento, em geral. Mas senhas criptográficas seriam decifradas com muita facilidade, e muitas contas bancárias e comunicações cifradas ficariam expostas. Então para fundamentar a segurança de suas senhas a criptografia precisaria arquitetá-las na resolução de algum problema realmente intratável(problema em que é impossível construir um algoritmo que sempre responda sim ou não, ele pode não responder ou responder errado), porque todos os da classe NP teriam passado à categoria de eficientes.
Para provar que P=NP deve-se construir um algoritmo com respostas ótimas, como o do método de força bruta, para os problemas NP-completos, de tal forma que se para qualquer um dos tais problemas se encontrar um algoritmo polinomial, então todos eles seriam resolvidos em tempo polinomial e, além disso, a classe NP seria rebaixada a P.