¿Cuál sería el impacto de P = NP? [cerrado]

18

Me estoy preparando para una prueba y no puedo encontrar una respuesta clara a la pregunta: ¿Cuál sería el impacto de probar que PTIME = NPTIME? Revisé Wikipedia y solo mencionó que tendría "un profundo impacto en matemáticas, IA, algoritmos ...", etc.

¿Alguien me puede dar una respuesta?

algorithms complexity latusaki
fuente
Esto no tiene nada que ver con el desarrollo de software. Cerré por ahora, pero les pregunté a los mods en Math.StackExchange si les gustaría que migrara esto por ustedes.
maple_shaft

Respuestas:

22

Lo primero que viene a la mente es que la seguridad de la criptografía de clave pública actualmente depende de la incapacidad de resolver los problemas matemáticos de fuerza bruta que se encuentran en la clase de dificultad NP. Si P = NP, todo lo que depende de PKC (incluido HTTPS, lo que significa que toda la infraestructura moderna de comercio electrónico en todo el mundo ) tendría que ser reelaborado.

Mason Wheeler
fuente
44
Aseguraría que hay algoritmos que se ejecutan en tiempo polinómico. Entonces solo sería una cuenta regresiva para encontrar esos algoritmos y luego kaboom, por así decirlo.
Ingeniero mundial
77
Una prueba implicaría encontrar un algoritmo de tiempo polinómico para un problema de NP completo. Y cuando encuentre un algoritmo polinomial, puede usarlo para resolver todos los demás problemas NP-completos reduciendo los problemas a una forma común. Esto significa que una prueba para P = NP y los algoritmos que lo usan aparecerán al mismo tiempo.
Oleksi
77
Por supuesto, los factores constantes pueden ser tan grandes para hacer de esto solo un problema teórico ... por algún tiempo.
quant_dev
17
Cuando encontramos un algoritmo de este tipo, todavía podría tener un factor constante horriblemente alto o ser de un grado tremendo (n ^ 10000 es polinomial, pero para muchos propósitos prácticos es mucho peor que una pequeña complejidad exponencial). Por supuesto, sería una señal de advertencia para todos alejarse de los viejos métodos, como nos alejamos del DES antes de que se pruebe que tiene solución, pero la economía mundial no colapsaría de inmediato. Solo piense en el dinero en sí mismo: en última instancia, todos saben que en realidad no funciona a menos que usted crea en él, pero el comercio global todavía funciona bien.
Kilian Foth
55
Probablemente recurriríamos al uso de pads únicos. Amazon podría enviarle por correo una unidad de memoria USB de 1 concierto que funcionaría con su sitio y lo retendría por el resto de su vida.
Macneil
18

Esto se trata en El estado del problema P versus NP . Definitivamente vale la pena leerlo.

Algunos puntos destacados del artículo (citado de la sección ¿Qué pasaría si P = NP? ):

  • La criptografía de clave pública se vuelve imposible.
  • Dado que todos los problemas de optimización de NP-complete se vuelven fáciles, todo será mucho más eficiente. El transporte de todos los formularios se programará de manera óptima para mover personas y mercancías de manera más rápida y económica. Los fabricantes pueden mejorar su producción para aumentar la velocidad y generar menos desperdicio.
  • Aprender se vuelve fácil usando el principio de la navaja de afeitar de Occam: simplemente encontramos que el programa más pequeño es consistente con los datos. El reconocimiento casi perfecto de la visión, la comprensión y traducción del lenguaje y todas las demás tareas de aprendizaje se vuelven triviales. También tendremos predicciones mucho mejores del clima y los terremotos y otros fenómenos naturales.
  • P = NP también tendría grandes implicaciones en matemáticas. Se podrían encontrar pruebas cortas y completamente lógicas para los teoremas, pero estas pruebas suelen ser extremadamente largas. Pero podemos usar el principio de la maquinilla de afeitar Occam para reconocer y verificar las pruebas matemáticas, como se suele escribir en las revistas. Luego podemos encontrar pruebas de teoremas que tienen pruebas de longitud razonable, por ejemplo, en menos de 100 páginas. Una persona que demuestre que P = NP caminaría a casa desde el Instituto Clay no con un cheque de $ 1 millón sino con siete (en realidad seis, ya que la Conjetura de Poincaré parece resuelta).
vinaykola
fuente
2
No veo cómo P = NP implica que la criptografía de clave pública es imposible. Sugiere (pero no implica) que las implementaciones actuales no son tan difíciles de romper como pensábamos anteriormente. Pero como otros han señalado, si las constantes relevantes en un algoritmo de reducción de tiempo óptimo son extremadamente grandes, entonces P = NP no tendría ningún impacto en la criptografía de clave pública.
Emory
+1 para el tercer punto: todos saben que P = NP afectaría a la criptografía, pero por alguna razón rara vez escuchas cómo afectaría literalmente a todas las demás disciplinas informáticas del planeta.
BlueRaja - Danny Pflughoeft
@emory: No pretendo ser un experto, pero entiendo que si se encontrara un algoritmo así, incluso con una constante bastante alta, tendríamos que repensar por completo nuestro enfoque. Además, ¿quién puede decir que una vez que se encuentra un algoritmo, no podemos encontrar otro con una constante más pequeña? Un algoritmo desbloquearía todos los demás problemas de NP completo también. Por lo tanto, el efecto inmediato puede no ser grande, pero habría que pensar mucho en cambiar todos los sistemas existentes.
vinaykola
La primera vez que escuché sobre el principio de la navaja de afeitar de Occam. Cosas interesantes ...
UmNyobe
@vinaykola probar que P = NP no implica encontrar un algoritmo. Por supuesto, encontrar un algoritmo sería la forma más directa (pero no la única) de probar P = NP y luego, si las constantes fueran razonables, podríamos abordar los problemas que planteó.
emory
7

La mayoría de los problemas completos de NP tienen aplicaciones "interesantes" de la vida real. P=NPtendrá muchas consecuencias:

  • Será posible resolver exactamente los problemas de optimización que actualmente se aproximan. Este es el caso del problema del vendedor ambulante y el problema de la programación del trabajo
  • Rompe algunas medidas de seguridad que se basan en el hecho de que el tiempo de cálculo requerido es enorme. Por ejemplo, muchos esquemas de encriptación y algoritmos en criptografía se basan en la factorización de números, el algoritmo más conocido que tiene una complejidad exponencial. Estos algoritmos serán inútiles si se encuentra un algoritmo polinomial.

La conclusión es sobre la naturaleza de los problemas que se sabe que son NP completos. Estos no son solo problemas creados por pocos científicos en una ubicación remota para entretenerse. Se pueden expresar en términos comerciales. De hecho, a algunos entrevistadores de trabajo les gusta ocultar problemas NP-completos en sus preguntas para evaluar a los candidatos.

UmNyobe
fuente
3
Si bien la factorización de enteros es un problema difícil, vale la pena señalar que no se sabe que sea NP completa.
dan_waterworth
44
@dan_waterworth: No se sabe si la factorización entera es NP-hard, pero se sabe que está en NP. [A menudo parece que la gente dice "NP-complete" cuando quieren decir "en NP" o "NP-hard". En cierto modo, sería como si alguien dijera "menor o igual que" en una situación en la que "menos que" sería más preciso.]
Macneil
5

Estas posibilidades están cubiertas en los cinco mundos de Impagliazzo .

Aquí hay algunos puntos para llevar:

  • La inteligencia artificial podría dar un gran salto. Por ejemplo, con suficientes "datos de entrenamiento", los circuitos más cortos para producir las salidas correctas de las entradas representarían el mejor método de traducción. En particular, sería trivial tener un perfecto reconocimiento de voz y traducción del idioma. Llevando esta idea más lejos, si sus datos de entrenamiento son películas ganadoras de un Oscar, puede generar más películas ganadoras de un Oscar para usted.

  • Los algoritmos que se enseñan en las escuelas serían radicalmente diferentes. En lugar de aprender tantas técnicas algorítmicas diferentes , los cursos se centrarían en reducir los problemas para verificar las respuestas correctas. Esto simplificaría enormemente la programación.

  • La economía se volvería mucho más eficiente. Habría interrupciones, incluso desplazando a los programadores. La práctica de la programación en sí misma consistiría más en recopilar datos de capacitación y menos en escribir código. Google tendría los recursos para sobresalir en un mundo así.

  • Debido a que la criptografía de clave pública estaría "fuera", Amazon necesitaría enviarle un bloc de notas único en una memoria USB para realizar transacciones seguras.

  • Las pruebas matemáticas pueden generarse y verificarse automáticamente.

En general, introduciría una singularidad tecnológica; Las implicaciones de P = NP serían de largo alcance. Además, Lance Fortnow aborda este punto en una publicación de blog separada que deberías leer.

Macneil
fuente
-1

El impacto de probar P = NP incluiría un renovado interés en encontrar un algoritmo de reducción. La gente también trataría de encontrar algunos límites inferiores en las constantes asociadas con el algoritmo de reducción.

Probar P = NP no sería tan significativo como afirman otras respuestas, porque podría presentarse en forma de prueba de conocimiento cero. Conocer P = NP sin conocer el algoritmo de reducción sería poco diferente de la situación actual.

Imagine si alguien demostrara que el algoritmo de reducción existe pero es O (sqrt (n) + 2 ^ 4096).

emory
fuente
1
En realidad, existe un algoritmo de reducción explícito que está en P si y solo si P = NP. Consiste en iterar sobre todos los programas posibles y ejecutarlos en paralelo hasta que uno encuentre la solución.
Arthur B
@ArthurB fascinante. Suponiendo que P = NP, ¿cuál es el orden del algoritmo?
emory
Es desconocido, pero es el orden óptimo. scholarpedia.org/article/Universal_search
Arthur B
1
@ArthurB así que si P = NP y el algoritmo de reducción es O (n ^ 99999999) ¿P = NP sigue siendo un gran problema?
emory