La segunda cosa que sucedería es que ganarías el premio Clay Mathematics Institute de $ 1 millón por resolver el problema P vs. NP. P vs. NP es uno de los seis problemas restantes con un premio de $ 1 millón. (La conjetura de Poincaré ya ha sido resuelta). Digo “segundo” porque hay un período de espera de 2 años después de que su solución se publique en una revista.
Lo primero que sucedería es que interrumpirías todo el campo de la criptografía. Esto amenazaría todas las formas de seguridad de Internet. Bitcoin y otras criptomonedas serían inútiles con la mera especulación de que las claves privadas podrían calcularse para permitir transacciones falsificadas. Las transacciones bancarias y de tarjetas de crédito por Internet ya no se considerarían seguras. Los archivos cifrados, archivos, discos, teléfonos y conexiones a Internet serían vulnerables. Su automóvil (con cerraduras electrónicas) sería más fácil de robar.
Una solución polinómica de alto orden para un problema NP-hard o NP-complete no rompería de inmediato toda la criptografía, pero estimularía la búsqueda de soluciones más eficientes. Es probable que tengan éxito. Hemos visto que esto sucede con RSA, Diffie-Hellman y otros algoritmos de clave pública que dependen de la dificultad del problema del logaritmo discreto (incluida la factorización). El descubrimiento de soluciones más rápidas que exponenciales (estas no son NP-hard) ha llevado a contramedidas como curvas elípticas y teclas más largas, por lo que estos algoritmos aún son seguros por ahora.
- ¿Cuál es la mejor manera de aprender el aprendizaje automático aprovechando mi sólida formación matemática?
- ¿Hay alguna prueba matemática de que los lenguajes de computadora modernos pueden representar cualquier algoritmo finito usando una cantidad finita de código?
- ¿Cuál es la mejor manera de aprender geometría algebraica si uno no está interesado en usarlo para propósitos teóricos numéricos, sino más bien para aplicaciones en física teórica e informática teórica?
- ¿Qué papel juega la habilidad matemática en la ingeniería informática o la codificación?
- Si f (n) es O (g (n)) yf (n) es O (h (n)), ¿significa que g (n) es O (h (n))?
Incluso si finalmente no se encuentran soluciones polinómicas de bajo orden para P = NP, la mera prueba de P = NP sería extremadamente preocupante. Creemos firmemente que P = NP es falso simplemente porque muchas personas han intentado y no han podido encontrar un ejemplo. Hay más de 3000 problemas conocidos de NP-completo. Si resuelves uno, los resuelves todos. Ahora has interrumpido una de las creencias más arraigadas (pero no comprobadas) en todas las matemáticas. Nada está a salvo ahora.
Así es como P = NP rompe la criptografía. Suponga que tiene una función de descifrado p = f ( c, clave ), donde c es el texto cifrado y p es el texto sin formato. Construya un circuito lógico que implemente f con entrada fija c y compare la salida con el texto plano conocido o adivinado, p . El circuito emite un 1 si es igual, 0 de lo contrario. A continuación, establezca uno de los bits clave en 0 y pregunte a su solucionador SAT de tiempo polinómico (hecho posible por P = NP) si hay una solución. Si no, cambie el bit de clave a 1. Luego repita para cada bit de la clave. Si el solucionador SAT se ejecuta en tiempo O ( n ^ k ) para algún exponente k (actualmente todavía grande), entonces la clave se puede encontrar en el tiempo O ( n ^ ( k +1)). Dado que esto es más rápido que la búsqueda de fuerza bruta ( O (2 ^ n )) para n suficientemente grande independientemente de k , el cifrado está roto.
