Estava lendo esses dias esse artigo aqui da ACM sobre o estado atual da arte na tentativa de provar se P é igual ou diferente de NP, e algumas observações me fizeram perceber algo que não tinha reparado antes.
Todos nós sabemos que a segurança da criptografia de chave pública (utilizada para transferir dados de modo seguro por uma rede de computadores) se baseia fortemente na dificuldade de fatorar números grandes em primos (também grandes). E existe toda a lenda de que se alguém provar que P=NP, toda a segurança vai por água abaixo, o que nos leva a supor que o problema de fatorar números seja NP-completo. Entretanto, no artigo citado o autor afirma que não se sabe se esse problema é NP e acredita-se realmente que ele não seja. Então eu me pergunto porque existe esse alarde todo sobre a segurança da criptografia quando se fala sobre P = NP. Tá faltando alguma coisa… se P for igual a NP significaria que todos os problemas poderiam ser resolvidos em tempo polinomial? Até aqueles que não se sabe a que classe pertencem?
Eu to perdendo algum detalhe…