Stephen Cook, en la Universidad de Toronto, publica en 1971 "The Complexity of Theorem-Proving Procedures", donde formula con precisión matemática la pregunta que se convertiría en el problema abierto más importante de la informática teórica: si todo problema cuya solución puede verificarse rápidamente (en tiempo polinómico, clase NP) puede también resolverse rápidamente desde cero (clase P), o si existen problemas fundamentalmente más difíciles de resolver que de comprobar. Cook demuestra que el problema de satisfacibilidad booleana (SAT) —determinar si existe una asignación de valores verdadero/falso que haga cierta una fórmula lógica dada— es "NP-completo": cualquier otro problema de la clase NP puede traducirse a una instancia de SAT en tiempo polinómico, de modo que si alguien encontrara un algoritmo rápido para resolver SAT, automáticamente tendría un algoritmo rápido para resolver todos los problemas de NP. El resultado, descubierto de forma independiente por Leonid Levin en la Unión Soviética el mismo año (de ahí su nombre alternativo, teorema de Cook-Levin), sienta las bases de la teoría de la NP-completitud que Richard Karp extendería en 1972 a otros 21 problemas clásicos. La pregunta P versus NP permanece sin resolver y es uno de los siete "Problemas del Milenio" del Clay Mathematics Institute, con un premio de un millón de dólares para quien lo demuestre o refute.