P vs NP

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.

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.