9 de octubre de 2026
P vs NP: la guía del gato ninja para ganar un millón de dólares
El 7 de octubre de 2026, Vitalik Buterin escribió en X un hilo que se leyó como una advertencia sobre computación cuántica y era otra cosa. El tema era la propuesta de Justin Drake de pasar a “modo búnker” y migrar fondos a direcciones nuevas, ante el riesgo de que la matemática acelerada por IA empiece a romper la criptografía de retículas. Y en medio del argumento, casi al pasar, aparece la frase que sostiene todo lo demás:
Teóricamente, por supuesto que es posible que los hashes se rompan también (por ejemplo, P = NP implicaría eso). Pero creo que P = NP es muy improbable. E intuitivamente, es mucho más probable que un objeto matemático no tenga ninguna estructura explotable (como los hashes pretenden), a que tenga exactamente tres formas de estructura explotable y no una cuarta secreta que todavía no descubrimos.
Buterin no estaba discutiendo el problema del milenio. Lo estaba usando como piso. Y ahí está la rareza que este artículo quiere mirar de frente: el mundo digital entero está parado sobre una conjetura que nadie sabe demostrar, apostando a que es verdadera. Cada firma, cada hash, cada bóveda, cada mensaje cifrado que mandás por día es una apuesta a que P ≠ NP.
Seis pasos y nueve láminas, con un millón de dólares esperando en una bóveda. El recorrido se puede hacer entero creyendo que la historia termina en “nadie sabe, y si P = NP se cae todo”. No termina ahí: la conjetura que sostiene al mundo digital no es la que la criptografía necesita, y de eso trata lo que sigue.
Paso 1: P — lo que se resuelve rápido

P es la clase de los problemas que una computadora resuelve en tiempo polinomial: el trabajo crece de forma razonable cuando crece la entrada. Ordenar una lista, multiplicar dos números, encontrar el camino más corto en un mapa. Decir “rápido” acá es una promesa matemática sobre el crecimiento, no sobre los segundos: un algoritmo puede ser polinomial y sin embargo chico al lado de otro polinomial mil veces peor.
Y conviene decirlo de entrada, porque es la mitad del malentendido: P no es “lo que las computadoras pueden hacer”. Es lo que pueden hacer en el peor caso imaginable de cada tamaño. En la práctica hay problemas NP-difíciles que se resuelven todos los días: los programas solvers de SAT despachan instancias industriales con millones de variables, en verificación de hardware y planificación. La teoría habla del peor caso; la ingeniería vive del caso promedio.
Paso 2: NP — lo que se verifica rápido

NP es la clase de los problemas cuya solución, una vez que alguien te la da, podés comprobar rápido. El Sudoku: llenarlo desde cero puede llevar una eternidad; mirar una grilla llena y decir “sí, está bien” te lleva un minuto. El problema del viajante: encontrar la ruta más corta entre cincuenta ciudades es un infierno; verificar que una ruta propuesta mide lo que dice, no.
Y acá entra el ejemplo que a nosotros nos importa: factorizar un número enorme. Multiplicar dos primos de mil bits es instantáneo. Recuperar esos primos a partir del producto es —hasta donde sabemos— imposible en la práctica. RSA, ECDSA, Diffie-Hellman, la firma con la que transferís plata: todo eso vive de esa asimetría.
Con una precisión que después va a ser la clave del artículo: factorizar está en NP y también en co-NP, y no se sabe si es NP-completo. Se cree que no lo es. Guardá ese dato, porque es el que rompe el relato optimista de “si P ≠ NP, mi criptografía está a salvo”.
La matriz de diagnóstico

| Dimensión | P | NP |
|---|---|---|
| Resolver (crear la respuesta) | Fácil y eficiente | Terriblemente difícil |
| Verificar (revisar la respuesta) | Fácil y eficiente | Fácil y eficiente |
| El mundo real | Multiplicar 15 × 15 | Romper la seguridad de un banco |
La tabla tiene una trampa escondida: P está contenido en NP. Todo lo que podés resolver rápido, obviamente podés verificarlo rápido. La pregunta del millón no es si P y NP son distintos en general —eso nadie lo duda— sino si lo son del todo, o si esa diferencia es una ilusión que se evapora cuando encontramos el truco correcto.
Un número para dimensionar el candado: el récord mundial de factorización (RSA-250, febrero de 2020) llegó a 829 bits y costó unas 2.700 años-CPU repartidos entre decenas de miles de máquinas. RSA-2048 sigue intacto. El margen no es del doble: es astronómico, y es la razón por la que vivimos tranquilos.
Paso 3: la gran pregunta

La pregunta es una sola frase, y es tan simple que parece una trampa:
¿Todo problema cuya solución se puede verificar rápido también se puede resolver rápido?
P = NP significa que verificar y resolver son, en el fondo, el mismo trabajo. P ≠ NP significa que existen problemas genuinamente difíciles: que hay una flecha que no se puede dar vuelta.
La formuló Steve Cook en 1971 y Leonid Levin en 1973, pero la intuición es más vieja: en 1956 Kurt Gödel le escribió a John von Neumann preguntándose cuánto costaría, en pasos, encontrar una demostración, comparado con chequearla. Nadie contestó esa carta. En el año 2000, el Clay Mathematics Institute la puso en su lista de siete Problemas del Milenio, con un millón de dólares por cada uno. Se resolvió uno solo: Poincaré, en 2003. Grigori Perelman rechazó el premio.
Paso 4: imagina el caos

Si P = NP fuera cierto, se abren dos mundos al mismo tiempo.
La rama utópica es la que se cuenta en las charlas: optimización perfecta, diseño instantáneo de medicamentos, plegado de proteínas, logística, IA sin techo, demostraciones matemáticas encontradas por máquina. Todo lo que hoy resolvemos a fuerza bruta o por aproximación se volvería exacto.
La rama apocalíptica es la que nos importa: se caen RSA y las curvas elípticas, se caen los hashes, se cae la firma de todo lo que alguna vez firmaste. No habría “privacidad más débil”: no habría privacidad. Cualquier mensaje cifrado guardado hoy es un mensaje en claro del futuro, porque el atacante solo tiene que esperar a que llegue el algoritmo.
Tres matices que suelen quedar afuera y que hay que decir:
- La caída no tiene por qué ser instantánea. Un algoritmo polinomial puede ser un polinomio con exponente absurdo: si el mejor algoritmo para SAT corre en n^1000, tu criptografía sigue en pie en la práctica. P vs NP pregunta por la forma de la curva, no por el reloj.
- La demostración podría no dar un algoritmo. Si alguien prueba P = NP de forma no constructiva —por contradicción, o con un argumento que no produce la máquina—, gana el millón y no rompe nada. Es un caso raro pero perfectamente concebible.
- Los computadores cuánticos no son un atajo a P = NP. Shor (1994) rompe RSA y las curvas, sí, pero porque la factorización tiene estructura algebraica explotable —no porque el cuántico resuelva NP-completo. Ningún problema NP-completo se sabe resolver en tiempo polinomial cuántico, y se cree que no se puede. Grover solo da una raíz cuadrada de ventaja. La computación cuántica no amenaza el andamio de P ≠ NP; lo amenaza por otro lado.
El caso Vitalik: hashes, retículas y el ruido que sí importa

Volvamos al hilo del 7 de octubre, porque tiene una lección de método. Buterin no estaba señalando a P = NP como el peligro. Al contrario: estaba diciendo que, para los hashes, P = NP es el único peligro real, y que por eso mismo los hashes son la parte más sólida del ecosistema. Un hash está diseñado para no tener ninguna estructura aprovechable. Y es mucho más plausible que un objeto matemático no tenga estructura, que un objeto matemático tenga tres formas de estructura y a ninguna de ellas se le haya escapado la cuarta.
El peligro que él sí ve está en otro lado: las retículas (ML-DSA, FHE, lattice-based), la criptografía post-cuántica que todo el mundo está adoptando justamente porque las curvas elípticas van a caer. El argumento, en sus palabras, es el de las “calaveras en el placard”: factorizar se creía difícil hasta que décadas de matemáticos inteligentes lo degradaron de 2^(n/2) a 2^O(n^(1/3)) y obligaron a que las claves RSA midan 400 bytes en lugar de 64. ¿Y si hay mejoras de ese calibre, escondidas para las retículas, que nosotros no somos lo bastante inteligentes para encontrar pero un bot sí? Su recomendación práctica: para todo lo basado en retículas, multiplicá los tamaños de clave por diez; y donde sea posible, quedate con hashes.
Esto no contradice el resto del artículo: lo completa. Hoy la amenaza concreta a la criptografía no es P = NP. Es criptoanálisis real, asistido por IA, contra supuestos de dureza concretos. Y sin embargo el lugar donde la conversación siempre termina es el mismo: (por ejemplo, P = NP implicaría eso). Es el piso del edificio, y todos sabemos que está ahí.
La parte que rompe el relato: P ≠ NP no alcanza
Acá viene el punto que en un artículo sobre soberanía no se puede saltear.
P ≠ NP no te da criptografía. Todo lo que usamos —hashes que no se pueden invertir, firmas que nadie puede falsificar— se apoya en algo más filoso: funciones de un solo sentido, es decir, problemas difíciles en el caso promedio, no solo en el peor caso. Y el caso promedio es un mundo completamente distinto del que pregunta P vs NP.
Russell Impagliazzo lo contó en 1995 con un ejercicio que merece estar en cualquier curriculum: los cinco mundos posibles.
- Algorithmica: P = NP. La criptografía es imposible.
- Heuristica: P ≠ NP, pero los problemas difíciles son fáciles en el caso promedio. La criptografía también es imposible.
- Pessiland: existen problemas difíciles en el caso promedio, pero no existen funciones de un solo sentido. P ≠ NP es verdadero y sin embargo no hay criptografía de ningún tipo. Tampoco hay generadores pseudoaleatorios: el mundo es frío, determinista y legible por cualquiera.
- Minicrypt: existen funciones de un solo sentido. Hay hashes, hay cifrado simétrico, hay MACs. No hay criptografía de clave pública: no hay firmas, no hay intercambio de claves, no hay blockchains.
- Cryptomania: existen funciones de un solo sentido con trampa. Hay clave pública, hay firmas, hay dinero digital. Es el mundo donde vivimos —o el que suponemos que habitamos.
La lección es que la criptografía no vive de P ≠ NP. Vive de una apuesta más fina: que la dureza del peor caso se puede fabricar y transportar hasta tu llave, en el caso promedio, con una distribución que vos controlás. Y esa apuesta es más fuerte que la otra: si existen funciones de un solo sentido, entonces P ≠ NP (porque invertir es verificar, y encontrar la preimagen es resolver). El recíproco no se sabe. Es decir: probar que P ≠ NP sería un gran avance en matemática y no un seguro para tu privacidad.
Y hay un detalle más. Acordate de factorización: está en NP y en co-NP y no se cree que sea NP-completa. Es decir que la dureza de RSA no se deduce de P ≠ NP ni aunque mañana alguien demuestre P ≠ NP con todas las de la ley. Vivimos en una casa con dos cimientos: uno visible y venerado (P ≠ NP) y otro real y mucho más frágil (la dureza del caso promedio). Cuando se habla de “seguridad demostrada”, casi siempre se está hablando del primero.
La llave también es la puerta
“Modo búnker” se puede resumir en una frase: mudá tus fondos a direcciones frescas, que nunca hayan firmado nada, para que tu clave pública siga escondida detrás del hash de la dirección. La criptografía es correcta: si la clave pública nunca se reveló, no hay de dónde sacar la privada —ni con cuántica ni sin ella—. El consejo es sólido para un tesoro.
El problema es que en lo que construimos la llave no custodia un tesoro: es un nombre.
En RHM Seguros el correo corporativo no tiene contraseña: entrás conectando la wallet y firmando un mensaje con un nonce. En Ius y ChatWallet la identidad es el par de llaves: la norma del vínculo Ğ1 que escribimos son dos firmas cruzadas que declaran que una dirección 0x… y una cuenta g1… son la misma persona, y ese vínculo queda en la cadena. Firmamos para entrar, para identificarnos, para certificar que alguien es alguien, para que otro pueda leer lo que publicamos. Si la dirección que te identifica tiene que quedar virgen para siempre, dejás de poder firmar — es decir, dejás de poder ser.
Y mudarse no es gratis. En Ğ1 v1 una llave era una identidad: cambiarla era revocar la identidad y juntar cinco certificaciones nuevas, con dos meses de ventana y la paciencia de cinco personas. En Duniter v2 —el que corre Ğ1 desde marzo de 2026— existe identity.changeOwnerKey: la identidad sobrevive al cambio de llave, pero la migración la firmás con la llave nueva y queda on-chain, con una ventana en la que la llave vieja todavía puede revocarla. Es exactamente lo contrario de esconderse detrás de un hash: es un acto público, con testigos.
La respuesta no es esconder la llave: es separarla. Una llave para firmar, otra para custodiar. Que la que te identifica no tenga valor, y que la del valor casi no se use. En el protocolo eso ya existe (contratos con jerarquía de llaves, sesiones que caducan, y el camino hash-only que Ethereum está tomando). En la experiencia de usuario todavía no tiene forma — y ahí es donde nuestros proyectos son, en el fondo, un experimento.
Un búnker asume que la llave es solo una caja fuerte. Cuando la llave también abre la puerta de tu casa, la estrategia a largo plazo no es mudarse: es tener dos.
Paso 5: acepta la realidad

La encuesta de referencia la hace William Gasarch cada siete años, y el resultado es estable: en 2002, 61 de 100 encuestados creían que P ≠ NP. En 2012, 126 de 152 (83%). En 2019, 109 de 124 (88%). La creencia dominante es fuerte, pero fijate que no es unanimidad, y que entre los pocos que se juegan por P = NP hay gente seria.
Más interesante que el porcentaje es por qué no hay demostración. Y acá la teoría de la complejidad tiene una respuesta inusualmente concreta: las barreras. Hay tres, y están probadas:
- Relativización (Baker, Gill y Solovay, 1975): existen oráculos que hacen P = NP y oráculos que hacen P ≠ NP. Cualquier técnica que funcione igual con o sin oráculo —la diagonalización, por ejemplo— no puede resolver la pregunta.
- Pruebas naturales (Razborov y Rudich, 1997): el gran método para probar imposibilidades en circuitos tiene una propiedad que, si se cumple a rajatabla, también rompería la criptografía que creemos segura. Probar P ≠ NP con esas herramientas sería probar algo que implicaría la falsedad de una creencia que nadie quiere abandonar.
- Algebrización (Aaronson y Wigderson, 2009): la técnica que supera a las dos anteriores también queda bloqueada por una versión algebraica del argumento de los oráculos.
Traducido: no es que nadie haya encontrado la demostración. Es que las técnicas conocidas están formalmente descartadas, y cada una fue descartada por un teorema. Por eso P vs NP es distinto de otros problemas abiertos: la dificultad no está en la falta de intentos, está en que sabemos que los intentos de cierto tipo no van a funcionar.
Y hay un pliegue más incómodo: es concebible —no probado, concebible— que P ≠ NP sea independiente de ZFC, es decir que ni la proposición ni su negación se puedan demostrar con los axiomas standard de la matemática. En la encuesta de 2012, un 3% eligió esa opción. Existen resultados condicionales (Ben-David y Halevi, 1992) que muestran que, bajo ciertos supuestos de dureza criptográfica, P ≠ NP sería indemostrable en fragmentos débiles de la aritmética. No es una fantasía de café: es una posibilidad que la gente seria anota.
¿Significa esto que el campo está congelado? No. En 2025, Ryan Williams demostró que toda máquina de Turing multitinta que corre en tiempo t se puede simular en espacio O(√t · log t) —la primera mejora sustancial en 50 años sobre el resultado de Hopcroft, Paul y Valiant (1975). Es un resultado sobre alrededor de la pared: la relación entre tiempo y memoria, los límites de la computación en general. El problema del millón sigue intacto, y la teoría sigue avanzando.
Paso 6: cobra tu millón (o ríndete como todos)

Digamos que mañana tenés la demostración. ¿Cobrás?
Las reglas del Clay, revisadas en 2018, tienen tres condiciones: la prueba se tiene que publicar en un “Qualifying Outlet”, tienen que pasar al menos dos años desde la publicación, y la solución tiene que haber logrado aceptación general en la comunidad matemática. Recién entonces el comité decide si vale la pena analizarla. No se aceptan envíos directos. La razón de los dos años no es burocracia: es experiencia acumulada.
Y tenemos el caso de estudio perfecto, del año pasado. En 2025, la revista Frontiers of Computer Science (Springer) publicó un artículo titulado “SAT Requires Exhaustive Search”, cuyo autor es Deputy Editor-in-Chief de la misma revista, con un resultado más fuerte que P ≠ NP. El comentario técnico de Eric Allender y Ryan Williams mostró que la cota inferior del teorema principal contradice un algoritmo de hace veinte años de Williams, que corre en tiempo O(d^(0.8n)) en el caso que el artículo declara imposible. Recomendaron retractar el artículo. El editor jefe se negó, diciendo que no encontraba evidencia de mala conducta; el comentario se publicó con el párrafo final recortado. Es decir: una demostración de P ≠ NP, publicada en una revista indexada, con un editor de la propia revista como autor, pasó la revisión por pares y sigue ahí. Eso es exactamente lo que los dos años y la “aceptación general” existen para filtrar.
¿Y las demostraciones asistidas por máquina? En junio de 2026 apareció en arXiv un trabajo que formaliza en Lean 4 un teorema llamado p_equals_np: 36 archivos, casi tres mil objetivos de compilación, cero sorry. La cadena es: el problema de pertenencia al politopo de pedigrí es polinomial, el TSP simétrico se reduce a ese problema vía la formulación de inserción multietapa, y por lo tanto P = NP.
Acá hay que ser precisos, porque en este blog ya contamos cómo Lean aseguró el circuito de Ironwood y no queremos decir dos cosas distintas: Lean no verifica que la matemática sea la correcta: verifica que la conclusión se sigue de las hipótesis que le diste. No es un oráculo de verdad, es el reemplazo del error humano en una cadena de deducciones. Todo el peso queda en el paso que no se mecaniza: que la formulación de inserción multietapa sea una reducción válida del TSP, y que la definición del politopo sea la que el paper dice. Un teorema impecable es tan fuerte como el modelado que lo alimenta —y arXiv, a diferencia de un Qualifying Outlet, no revisa nada.
Es la misma asimetría del artículo, dada vuelta: verificar es fácil, modelar no.
La bóveda

La última lámina deja una imagen mejor de lo que parece: el millón de dólares del Clay Institute sigue intacto, esperando en una bóveda cuya contraseña es fácil de verificar pero aparentemente imposible de resolver. La bóveda es, ella misma, el teorema. Es la asimetría hecha objeto.
Y esa asimetría es la que sostiene todo lo que vinimos contando en esta serie. La prueba de conocimiento cero con la que Zcash asegura un pool se verifica en milisegundos y se produjo en minutos: usamos la brecha a propósito, a favor. PeerDAS no descarga el bloque: muestrea unas celdas y sabe. La tela de confianza de Ğ1 no pide la verdad completa: pide cinco firmas que vencen y se renuevan. En los tres casos se hace el mismo movimiento epistémico —no hace falta tenerlo todo para saber que está bien—, y en los tres casos hay alguien aprovechando una asimetría entre producir y chequear.
Por eso P vs NP no es un acertijo de matemáticos. Es la pregunta sobre qué tipo de mundo habitamos: uno donde creer es más barato que saber, y donde ese descuento se puede fabricar a voluntad, o uno donde el atajo de la verificación se puede deshacer hacia atrás y todo lo que está guardado queda a la vista.
No sabemos cuál de los dos es el nuestro. Apostamos el sistema financiero, las comunicaciones, las identidades y las llaves de tus fondos a que es el primero. Hasta ahora la bóveda aguantó.
El millón sigue adentro. Y la pregunta sigue abierta, igual que en la primera lámina: si verificar es barato, ¿por qué resolver tiene que ser caro?