Nota sobre o problema P versus NP (II)

Um dos maiores mistérios não resolvidos da ciência da computação é o problema P versus NP. Ele faz uma pergunta simples: todo problema cuja solução pode ser rapidamente verificada pode ser resolvido com a mesma rapidez (Aqui, "rapidamente" significa em tempo polinomial)? Embora a questão tenha sido sugerida numa carta de John Nash em 1955, a formalização do problema é creditada a Stephen Cook e Leonid Levin. Apesar de décadas de esforço, ninguém conseguiu respondê-la definitivamente. Está intimamente relacionado o conceito de NP-completude. Se pelo menos um problema NP-completo puder ser resolvido eficientemente (em tempo polinomial), então isso implica que P é igual a NP. Este trabalho propõe que um problema NP-completo específico, ONE-IN-THREE 3SAT, pode ser resolvido eficientemente. Desta forma, provamos que P é igual a NP.