[Sugerencia de servicio: primero lea el último párrafo y luego vuelva a leer la respuesta completa]
La pregunta original era:
“Internet dice que si se encontrara un algoritmo para un problema de NP, la criptografía se descifraría fácilmente, eso no es cierto, ¿verdad?”
- ¿Cómo describirías a los miembros de la facultad en el departamento de CS de tu universidad?
- Si envío una aplicación Spark en mi computadora portátil a un clúster Yarn remoto, ¿debo instalar el binario Spark en los nodos de Hadoop?
- ¿El aprendizaje automático y la IA harán que la democracia sea obsoleta?
- ¿Cuál es el concepto de desrandomización en el contexto de la computación?
- ¿Qué tan bueno es NIIT Neemrana para CSE?
Más tarde se cambió a:
¿La existencia de un algoritmo polinómico para un problema NP-duro implica que podremos romper fácilmente la criptografía?
Las respuestas son: “esto es casi cierto” y “más o menos”, respectivamente.
Comencemos con algunas definiciones. Intuitivamente, en informática, un problema de decisión es una pregunta bien definida para la que la respuesta es “sí” o “no”. Un ejemplo de este tipo de problema es el siguiente (no es necesario que comprenda el problema en sí mismo para comprender el ejemplo): dadas tres variables [matemáticas] x_0, x_1, x_2 [/ matemáticas] que pueden tomar 0 o 1, ¿existe una asignación (es decir, una elección de valores para cada uno de ellos), de modo que la ecuación [matemática] (x_0 \ vee x_1) \ wedge (x_0 \ vee x_2) = 1 [/ matemática] sea verdadera. Esto parece fácil de resolver, ¿verdad? Simplemente marque todas las asignaciones [matemáticas] 2 ^ 3 [/ matemáticas] para las variables y obtendrá su respuesta. Pero, ¿qué pasa si hay 60 variables? Verificar las opciones 2 ^ {60} llevará mucho tiempo, y verificar las opciones 2 ^ {128} ya no es factible con la tecnología actual (y no se espera que esto cambie durante la vida útil).
Por otro lado, para una ecuación de la forma [math] x_0 \ oplus x_1 \ oplus x_2 = 0 [/ math] es fácil verificar si existe una solución (la respuesta es sí, para cualquier valor de [math] x_0 \ oplus x_1 [/ math] simplemente establece [math] x_2 = x_0 \ oplus x_1 [/ math]). En este problema, no importa cuántas variables tenga, responder el problema lleva la misma cantidad de tiempo.
En este momento, debe comenzar a sospechar que la dificultad de resolver el problema se mide de alguna manera con respecto al número de entradas, lo que llamamos “el tamaño del problema”. Así que ahora podemos definir qué significa “fácil”. Un problema “fácil” es uno que “puede resolverse en tiempo polinómico” (con respecto a su tamaño). Mi último ejemplo es de tal naturaleza. Está bien si no sabes lo que significa el tiempo polinómico. Solo piense en ello como alguna función en el número de entradas. El tiempo que lleva resolver el problema no puede ser mayor que la respuesta a esta función cuando se calcula sobre los valores apropiados. Usaré la palabra “fácil” entre comillas para enfatizar que quiero decir “se puede resolver en tiempo polinómico”. Más adelante, explicaré la diferencia entre fácil y “fácil”
La clase de complejidad P es el conjunto de problemas que sabemos cómo resolver en tiempo polinómico o menos, estos son los problemas “fáciles”. La clase de complejidad NP es el conjunto de problemas que no sabemos cómo resolver en tiempo polinómico, pero cuando se nos da una solución, sabemos cómo verificarlo en tiempo polinómico. En mi ejemplo anterior, si le doy una asignación para todas las variables involucradas, puede simplemente sustituirlas y verificar si la ecuación es verdadera. Antes de continuar, necesito introducir dos clases más de problemas, estos son los problemas NP completos y los problemas NP difíciles. Son un poco más difíciles de entender, así que tengan paciencia conmigo mientras trato de simplificarlo. La clase de problemas NP-completos es el conjunto de todos los problemas para los cuales, si pudiéramos encontrar una solución, también podríamos resolver cualquier problema NP. En otras palabras, suponga que tiene un algoritmo que resuelve un problema de NP completo, y se le pide que resuelva un problema diferente que está en NP (no necesariamente NP-completo). Puede traducir su problema NP en el problema NP-completo que sabe cómo resolver, resolverlo y luego volver a traducir la solución obtenida a su problema original. Está comprobado que cualquier problema en NP puede traducirse a cualquier problema de NP completo; eso es lo que está “completo” al respecto. Todavía necesito explicar qué NP-hard, pero lo trataré más tarde.
En cierto sentido, los problemas NP completos son los “más difíciles” entre los problemas NP (pero no los “más difíciles” entre todos los problemas). Debido a este proceso de traducción que mencioné, ser capaz de resolver “fácilmente” un problema de NP completo, significa que podemos resolver “fácilmente” cualquier problema de NP. O, en otras palabras, significa que todos los problemas del mundo son tan “fáciles” de resolver (recuerde que la palabra “fácil” tiene un significado especial como se definió anteriormente, y no debe confundirse con el significado normal de la palabra fácil).
La criptografía se basa en la idea de que realizar algunas operaciones es fácil (o a veces “fácil”, para las ramas más teóricas de la criptografía), pero invertirlas no lo es. El ejemplo que más me gusta es del libro de Andrew Tanenbaum (reformulación de memoria): es fácil tirar un vaso al suelo y romperlo, es mucho más difícil invertir el proceso y pegar las piezas de una manera perfecta. Si todos los problemas son tan fáciles, significa que no hay una brecha de dificultad que podamos usar, y esas son malas noticias para la criptografía. Entonces, volviendo a la pregunta original: si se encontró un algoritmo para resolver problemas NP-completos (no solo NP), la criptografía está condenada.
La segunda pregunta se refiere a problemas NP-difíciles. La definición exacta no importa aquí, ya que es suficiente decir que estos son al menos tan difíciles como los problemas NP-completos. Por lo tanto, resolverlos también significaría que la criptografía se puede descifrar “fácilmente”, pero como señala Julien Hué en su respuesta, aún puede no ser fácil en el sentido normal, ya que el “tiempo polinómico” aún puede ser grande.
Para el OP original, su pregunta es asombrosa, y no debe desanimarse por el hecho de que alguien la haya cambiado para hacerlo más complejo (sin ninguna razón IMO). Esto es bastante avanzado, así que espero haber hecho accesible la respuesta. No se avergüence de pedir aclaraciones en los comentarios, me complacerá proporcionarlas.
