Si el problema P versus NP se resuelve, de alguna manera, ¿cuál sería el mayor impacto?

Creo que P vs NP es una pregunta profunda. Con base en el progreso realizado hasta ahora para resolverlo, sabemos de hecho que la solución necesita superar tres obstáculos principales:
(1) Pruebas Relativizantes
(2) Pruebas naturales
(3) Pruebas de algebrización
Para una elaboración, consulte:
La respuesta de Jacob Minz a ¿Cuáles fueron los mejores intentos para resolver el problema P vs NP?

Las implicaciones plantean algunas preguntas:
(1) ¿Existe un sistema de prueba más allá de estos sistemas?
(2) ¿Existe un sistema de prueba donde el problema NP vs P es decidible, es decir, existe una respuesta verdadera o falsa?
(3) ¿Es posible que no existan sistemas de prueba donde se pueda resolver esta cuestión?

Posibilidades:
(1) No existe un sistema de prueba donde la pregunta NP vs P pueda ser resuelta. Si la prueba de esta afirmación está disponible, la pregunta NP vs P puede considerarse resuelta con impactos mínimos. Esto significa que esa declaración podría ser verdadera o falsa, pero no se puede construir ninguna prueba. O la afirmación no es verdadera ni falsa, y podemos probar ese hecho.
(2) Si finalmente aparece una prueba que dice P! = NP, todos esos resultados de alto impacto en la complejidad del circuito y la criptografía que se basa en ” declaración es verdadera a menos que P = NP ” sean seguros. Y la comunidad de la informática finalmente puede considerar que numerosos teoremas están completos en el sentido real de la palabra.
(3) Si surge una prueba profundamente investigada que pruebe P = NP, entonces la espada Damocles cae sobre la cabeza de todos los informáticos, confiando en que P! = NP para sus pruebas, todas las pruebas de dureza de los problemas caer en el sentido de la complejidad de la palabra. No necesariamente significa que alguna encriptación dura hasta ahora se romperá más rápido. Significa que hay una forma algorítmica de fuerza no casi bruta para romperlo, y eso lo hace filosóficamente más fácil.

Impacto:
(1) El mayor impacto será el cierre y el alivio de finalmente conocer la verdad.
(2) Las técnicas utilizadas para resolver NP vs P sin duda resolverán otras preguntas y aumentarán nuestra comprensión de las clases de problemas, su dureza y su capacidad de solución.

Estoy completamente de acuerdo con la respuesta que dio Alon, pero creo que hay ciertas cosas que mencionar. [math] P \ neq NP [/ math] tendrá un impacto mínimo, si no no, en la vida práctica ya que los criptosistemas seguirán siendo seguros como lo son hoy. Pero si se demuestra lo contrario, también creo que no veremos ningún impacto durante un largo período de tiempo.

Estoy de acuerdo en que si 3SAT es solucionable en tiempo polinómico, eso tendrá muchas repercusiones teóricamente, pero solo decir 3SAT, o en realidad cualquier problema NP-Complete, es solucionable en tiempo polinómico no afirma nada sobre su eficiencia en la implementación, por lo que Hasta ahora los aspectos prácticos están relacionados. En la parte superior de mi cabeza, no puedo encontrar un algoritmo único que se implemente en la vida real y tenga un tiempo de ejecución de [math] O (n ^ {100}) [/ math] (say).

De la manera en que funciona la informática teórica, primero se te ocurre un algoritmo para un problema específico que es eficiente en teoría, es decir, se ejecuta en tiempo polivinílico. Luego, mejora el algoritmo para que se ejecute a tiempo, que es un pequeño grado constante de [matemáticas] n [/ matemáticas], [matemáticas] n [/ matemáticas] es el tamaño de entrada. Puede suceder que [math] P = NP [/ math] pero la implementación de un algoritmo NP-complete necesita un tiempo que es [math] O (n ^ {10000}) [/ math] y también tiene un límite inferior correspondiente. Entonces estamos bien. Nada se rompe Las supercomputadoras pueden funcionar siempre que quieran romper el RSA, estamos bien, bueno, a menos que las computadoras cuánticas entren en escena. Entonces estamos jodidos de cualquier manera.

Eso depende de cómo se resuelva.

Si alguien demuestra que [matemáticas] \ mbox {P} \ neq \ mbox {NP} [/ matemáticas], que es el resultado esperado, la prueba probablemente tendrá tremendas repercusiones teóricas en matemáticas y ciencias de la computación. Se reescribirán los libros de texto, se revisarán los currículos del curso, será muy divertido.

En términos de un impacto práctico en la vida de las personas, esto será prácticamente inexistente. Todos creen [math] \ mbox {P} \ neq \ mbox {NP} [/ math] de todos modos, así que el hecho de saber que es cierto no importará en absoluto para ningún sistema físico, basado en computadora o de otra manera.

Pero si, por ejemplo, alguien demuestra que [math] \ mbox {P} = \ mbox {NP} [/ math] al exhibir un algoritmo de tiempo polinómico para, digamos, 3-SAT, podría haber más impacto. Muchos sistemas se reescribirán para aprovechar este avance fenomenal, aunque incluso eso depende de la eficacia práctica del algoritmo recién descubierto (el tiempo polinómico no es garantía de eficiencia: el tiempo de ejecución podría depender de una potencia muy alta de la entrada tamaño con coeficientes muy grandes).

El impacto en la criptografía de clave pública y los sistemas relacionados no será necesariamente significativo. El descubrimiento del nuevo algoritmo puede abrir un camino para invertir de manera práctica y eficiente las funciones unidireccionales, pero puede que no. Si lo hace, entonces el comercio electrónico y dichos sistemas pueden estar seriamente amenazados y necesitar una revisión rápida, lo que podría causar una interrupción importante en las finanzas, la industria y el comercio.

Existen otras alternativas (una prueba no constructiva de que [math] \ mbox {P} = \ mbox {NP} [/ math], o una prueba de independencia de algún sistema formal como ZFC). De nuevo, el impacto de una resolución depende profundamente de la naturaleza de esa resolución.

El mayor impacto sería estético . El problema P vs NP se convertiría, por ejemplo, en el ” teorema de Terrence Tao” . de nuestra generación tiene un nombre tan épicamente feo!

En una nota más seria, la teoría de la complejidad es una guía, no una evaluación inmediata y práctica de qué tan rápido se ejecutará un algoritmo. Por ejemplo, hay un algoritmo para invertir matrices en operaciones menores que [math] n ^ 3 [/ math]. Pero en la práctica, la implementación es, de hecho, más lenta en la mayoría de los casos. Este punto está implícito en las respuestas proporcionadas hasta ahora, pero sentí que valía la pena destacar las implicaciones más generales.

Saludos 😉

Hago todo tipo de cosas durante mi búsqueda de complejidad:

• ¿Qué geometría sigue la naturaleza? ¿Es superior la geometría euclidiana?
• ¿Por qué es tan importante la teoría de la turbulencia y qué la convierte en uno, si no el problema más difícil de resolver, tanto en física como en matemáticas?
• ¿Los números aleatorios son realmente aleatorios si se generan a partir de algoritmos?
• ¿Es sostenible la industria de las telecomunicaciones?

Entonces, el posible impacto es una gran imagen de todo a gran escala.

Mi solución geométrica: ¿podría resolverse el problema P versus NP para 2020? ¿Cuánto progreso se ha hecho al respecto?

Si se demuestra que NP se puede calcular en tiempo P, se pueden descifrar las contraseñas hash. En otro mundo, ninguna contraseña es segura, sino que pertenece a la banca por Internet, a las redes sociales, etc. Aunque hasta ahora no es posible, algunos de los problemas de NP pueden resolverse reduciéndolos a otro problema P.