¿Qué significaría si P = NP? ¿Cómo podrías intentar probarlo? ¿Cómo cambiaría el mundo?

Los pensamientos más populares sobre lo que significarían las consecuencias de P = NP giran en torno a cuáles serían las consecuencias sobre la tecnología y, posteriormente, la sociedad. Sin embargo, las implicaciones científicas y filosóficas serían, en mi opinión, más profundas. Mi intuición personal, estando de acuerdo con la mayoría del consenso científico, es que P! = NP. La forma en que se desarrolla la naturaleza observada cumple con P! = NP en un grado tan grande que probar P = NP revolucionaría toda la ciencia y la filosofía tal como la conocemos, por lo que no creo que P = NP. Si se demostrara que existe una solución que demuestra P = NP, eso nos otorgaría un ‘atajo’ para resolver muchos problemas computacionales que irían en contra de gran parte de lo que observamos de la naturaleza, incluidas las matemáticas, que volveríamos a evaluar Muchas de nuestras nociones fundamentales de cómo funciona la naturaleza.

Todo el comercio electrónico se volvería inseguro. Todas las técnicas prácticas conocidas para la comunicación electrónica segura quedarían obsoletas de repente. Habría consecuencias financieras negativas masivas y problemas peligrosos de seguridad nacional. Sería el Y2K que nunca sucedió.

Así que supongo que depende de quién lo descubrió y si el conocimiento se hizo público. Si se mantuviera en secreto, quien tuviera la prueba podría ejercer un poder enorme.

Depende de la prueba.

Si es una prueba no constructiva, entonces no habrá ningún efecto. El mundo tal como es hoy es el mundo donde la gente cree que P! = NP. Si resulta que P = NP, pero la prueba no es constructiva, solo significaría que existe una solución de tiempo polinomial para problemas de NP completo, pero no significa que eventualmente cualquiera pueda encontrar dicha solución. Quizás lo habrá, pero en unos pocos miles de años quizás.

Si es una prueba constructiva (quizás una solución de tiempo polinomial para el problema SAT), entonces significa que cada problema NP-completo pronto tendrá una solución de tiempo polinomial.

Depende de la prueba. La mayoría de las pruebas de complejidad de cómputo implica probar que un problema es traducible a otro problema conocido con complejidad de cómputo previamente probada. Si esta prueba adoptara el mismo enfoque, tendría un enorme impacto en las matemáticas y los campos derivados (lea toda la ciencia y la ingeniería), ya que proporcionaría una receta para resolver una serie de problemas que actualmente no se pueden resolver.

Más información aquí: http://en.wikipedia.org/wiki/P_v …

Los algoritmos criptográficos que son NP completos y, por lo tanto, necesitan una búsqueda exponencial para romperse, entonces serían polinómicamente solucionables. ¡La criptografía debería reinventarse!

Entonces podemos resolver problemas difíciles en nuestras computadoras porque todos los problemas que solucionamos usando nuestras computadoras están en tiempo polinómico.

y si esto se ha demostrado, el premio será de 1 millón y tal vez el premio Nobel