Comprobar una respuesta es barato. Encontrarla, hasta donde sabemos, no. Nadie ha demostrado que esa diferencia sea real.
Un problema está en P si existe un algoritmo que lo resuelve en tiempo polinomial en el tamaño de la entrada. Está en NP si, dada una respuesta candidata acompañada de un certificado, se puede verificar en tiempo polinomial que es correcta.
La pregunta es si esas dos clases coinciden. Formalmente hay que demostrar P = NP o P ≠ NP. La inclusión P ⊆ NP es inmediata: si sabes resolverlo rápido, sabes verificarlo rápido. La otra dirección es la que vale un millón.
El enunciado oficial del Clay lo escribió Stephen Cook, que es además quien inauguró el área en 1971.
En 1971 Stephen Cook demostró que existe un problema en NP tan duro como cualquier otro de la clase: la satisfacibilidad booleana. Si alguien encuentra un algoritmo polinomial para SAT, todo NP se derrumba en P de una vez. Leonid Levin llegó a lo mismo de forma independiente en la Unión Soviética.
Al año siguiente Richard Karp mostró que la lista de problemas con esa propiedad no era una rareza: exhibió veintiuno, todos ellos problemas prácticos que la gente ya intentaba resolver —el viajante, la mochila, el coloreo de grafos, la partición de conjuntos—. Hoy la lista pasa de varios miles.
Antes de eso, en 1956, Kurt Gödel le había escrito una carta a John von Neumann planteando esencialmente la misma pregunta: si encontrar una demostración de longitud n se puede hacer en tiempo proporcional a n o a n², en vez de recorrer todas las posibilidades. La carta se perdió durante veinte años.
Lo notable de P vs NP es que no sólo está abierto: se ha demostrado que ciertas técnicas no pueden resolverlo. Son tres barreras, y cada una mató una generación de intentos.
Relativización (Baker, Gill y Solovay, 1975). Si a las máquinas se les da acceso a un oráculo, existe un oráculo A con P^A = NP^A y otro B con P^B ≠ NP^B. Cualquier demostración que siga funcionando al añadir un oráculo —y la diagonalización clásica es así— no puede decidir la pregunta.
Pruebas naturales (Razborov y Rudich, 1994). Casi todos los intentos de demostrar cotas inferiores de circuitos comparten una estructura: exhiben una propiedad que es fácil de comprobar y que casi todas las funciones cumplen. Razborov y Rudich demostraron que si existieran generadores pseudoaleatorios suficientemente fuertes —cosa que la criptografía moderna da por cierta— ninguna demostración de esa forma puede funcionar.
Algebrización (Aaronson y Wigderson, 2008). Las técnicas que sí escapan a la relativización, basadas en aritmetizar circuitos, tropiezan con una versión algebraica de la misma barrera.
El resultado es que quien quiera resolver esto necesita una técnica que no sea ninguna de las tres, y nadie sabe todavía qué aspecto tiene.
Hay estructura intermedia. Richard Ladner demostró en 1975 que si P ≠ NP entonces existen problemas en NP que no están en P y tampoco son NP-completos. El grafo de isomorfismo es el candidato clásico, aunque en 2015 László Babai dio un algoritmo cuasipolinomial que lo empujó mucho más cerca de P.
Se sabe separar clases muy grandes. En 2011 Ryan Williams demostró que NEXP no está contenida en ACC⁰, la primera separación de ese tipo en décadas. Es un resultado celebrado y, a la vez, una medida de lo lejos que estamos: ACC⁰ es una clase de circuitos muy débil.
Casi todos apuestan lo mismo. En las encuestas informales que William Gasarch ha hecho entre teóricos desde 2002, alrededor del 80% cree que P ≠ NP. Eso no es evidencia matemática, pero dice dónde está el consenso.
Y si fuera P = NP, con un algoritmo eficiente y explícito, se caerían de un golpe la criptografía de clave pública, buena parte de la seguridad de internet y la idea misma de que verificar es más fácil que descubrir. Scott Aaronson lo resume diciendo que el mundo sería un lugar muy distinto: cualquiera que pudiera reconocer una buena demostración podría encontrarla.