Hay muchos tipos diferentes de formas en que P podría ser igual a NP.
Para elaborar, hay un artículo bien conocido de Impagliazzo (descrito en los cinco mundos de Impagliazzo) que describe cinco “mundos” diferentes, cada uno con diferentes grados de P = NP. Recomiendo encarecidamente leer el documento en sí, pero aquí hay una breve descripción del artículo vinculado:
- Algorítmica: P = NP o algo “moralmente equivalente” como algoritmos probabilísticos rápidos para NP. Este era el mundo que describí la semana pasada, pero mirando hacia atrás en el artículo de Impagliazzo, hace un trabajo mejor.
- Heuristica: los problemas de NP son difíciles en el peor de los casos, pero fáciles en promedio.
- Pessiland: los problemas de NP son difíciles en promedio, pero no existen funciones unidireccionales. Podemos crear fácilmente problemas NP difíciles, pero no problemas NP difíciles cuando conocemos la solución. Este es el peor de todos los mundos posibles, ya que no solo no podemos resolver problemas difíciles en promedio, sino que aparentemente no obtenemos ninguna ventaja criptográfica de la dureza de estos problemas.
- Minicrypt: existen funciones unidireccionales pero no tenemos criptografía de clave pública.
- Criptomanía: es posible la criptografía de clave pública, es decir, dos partes pueden intercambiar mensajes secretos a través de canales abiertos.
Está bastante claro que si P = NP en un sentido razonable (es decir, [matemáticas] NP \ subseteq BPP [/ matemáticas]) tenemos un problema real de criptografía. Ahora es fácil calcular cosas que pensamos que eran difíciles de calcular (como la función totient [math] \ varphi [/ math] de Euler utilizada en el esquema de cifrado RSA).
- ¿Puede un niño de diez años aprender Java, si es bueno en matemáticas?
- ¿Por qué SAS es mucho más rápido que R? Utilicé el código para encontrar los primeros k números primos en SAS y R para comparar su eficiencia, y los códigos son esencialmente los mismos, pero los resultados están fuera de mi mente.
- Si una persona tuviera un nuevo modelo de física fundacional de calidad nacido de la informática, no de las matemáticas, ¿cuál sería la mejor manera de presentarlo?
- Cómo aumentar la velocidad de cálculo de la función trigonométrica en una computadora
- ¿Cuál es una explicación para esta ecuación de números de punto fijo con signo?
Sinceramente, no sé cómo evolucionaría la criptografía a partir de ahí. Lo más importante que queremos de un esquema de cifrado es que el mensaje es fácil de cifrar, pero difícil de descifrar. Tener [math] NP \ subseteq BPP [/ math] pondría un serio obstáculo en la existencia de problemas como ese.
Sin embargo, también podríamos tener P = NP, pero los algoritmos de tiempo polinomiales que encontramos para los problemas de NP son terriblemente lentos, con factores constantes y exponentes masivos. En este caso, no cambiaría mucho.
