¿Qué pasaría si alguien prueba P = NP o P! = NP?

Primero, deberíamos hablar sobre el caso menos probable de P = NP que se está probando, y aquí, hay algunos casos a considerar:

1. P = NP está probado, pero de manera no constructiva, es decir, no se ha descubierto ningún algoritmo real.
2. P = NP, pero se encuentra un algoritmo embarazosamente lento, por ejemplo, el algoritmo se ejecuta en O (n ^ (1000)).
3. P = NP está probado y se ha encontrado un algoritmo rápido.

De hecho, sugiero que el caso 1 implica el caso 2: con la búsqueda universal de Levin, puede probar todas las máquinas de Turing hasta que encuentre una que funcione. El algoritmo será vergonzosamente lento, pero eventualmente funcionará y estará técnicamente ligado al tiempo polinómico. (Por razones técnicas, esta idea es ligeramente sospechosa, pero funcionará bajo supuestos “habituales” de la naturaleza de la prueba).

En el caso 2, el resultado sería realmente notable y probablemente conduciría a una búsqueda de una mejora con un algoritmo “real” para resolver el problema. No habría una consecuencia inmediata en nuestra vida diaria, excepto posiblemente que la prueba en sí sería útil para generar resultados de prueba más interesantes.

En el caso 3, otros comentaristas ya han discutido esto. El efecto neto para la sociedad será positivo, pero el impacto a corto plazo en realidad será problemático. Nuestros medios actuales de establecer intercambios financieros seguros se romperían. En efecto, utilizando mecanismos basados ​​en estándares, cualquier cifrado o falsificación de firmas “seguras” podría ser pirateado. El impacto sería que tendríamos que confiar en mecanismos que no están basados ​​en estándares (algoritmos no publicados) o en otras medidas de seguridad. Esto tomaría un tiempo para la transición, pero eventualmente, comenzaríamos a disfrutar los beneficios de tener una solución P = NP.

Si se prueba P! = NP, entonces habría poca probabilidad de causar un gran impacto en la vida cotidiana, excepto que las personas dejarían de buscar soluciones de tiempo polinomial reales para los problemas NP-Hard. Sin embargo, la prueba en sí misma podría conducir a ideas que podrían ser útiles.

En primer lugar, hay dos ventajas claramente diferentes.

P = NP es uno.

Ser capaz de resolver problemas arbitrarios de P en O (N ^ 4) es otra.

Francamente, la habilidad posterior es mucho más útil, porque tiene muchas, muchas más aplicaciones. La principal ventaja práctica del primero está en el cifrado de clave pública.

En ambos casos, Corea del Norte tendría una ventana * muy * limitada en la que utilizar sus conocimientos, antes de que se conozca en general. El mero hecho de que tal solución fuera posible en tiempo P (y que los NK tuvieran un P-solucionador rápido) llamaría inmediatamente la atención de todas las agencias de espionaje del mundo cuando NK intentara penetrar varias conexiones electrónicas corporativas y militares. No es tan difícil hacer ingeniería inversa en algo una vez que alguien te ha demostrado que se puede hacer (y, en particular, si puedes capturar información mientras lo hacen, lo que personas como la NSA podrían hacer después del primer descanso importante reveló el capacidad).

En términos prácticos: NK probablemente podría entrar y robar una gran cantidad de dinero de varias instituciones financieras, antes de que fueran desconectados del sistema mundial. Es probable que la ventaja sea una ingeniería inversa rápida, o que se obtenga de un desertor (imagine la tentación de desertar con ese tipo de secreto, que lo trataría como un rey por el resto de su vida a quien se lo haya dado).

Después de eso, todos lo tendrían, y tendríamos algunos avances científicos bastante increíbles (como un solucionador de P de solución corta es una cosa ENORME). NP = P requeriría que eliminemos o modifiquemos en gran medida la PKI, pero eso es todo para un impacto inmediato. Las mejoras a largo plazo provendrían de una solución polinómica para el problema de Travelling Saleman (que tiene muchas aplicaciones prácticas).

(La pregunta original era: ¿Qué pasaría si Corea del Norte obtuviera la prueba de que P = NP)

Kim Jong-Un tendría que ser acreditado por la prueba.

Si alguien prueba [matemática] P \ ne NP [/ matemática] entonces ocurrirá lo mismo que sucedió cuando el CERN encontró el bosón de Higgs, o cuando Wiles completó la prueba del teorema de Fermat: un pequeño y temporal circo mediático que rodeaba a las personas que lo demostraron , tal vez una medalla Fields y un libro de Simon Singh que detalla la historia del problema, y ​​así sucesivamente. Las personas que no estén interesadas en matemáticas o ciencias de la computación probablemente ni se darán cuenta. Lo esperábamos todo el tiempo; ahora ha sido confirmado, yay! Es sorprendente que haya personas realmente preocupadas por todas esas cosas cuando hay bocas que alimentar.

Sin embargo, las matemáticas utilizadas para demostrar esto necesitarán ser otra cosa. En el mundo matemático, la prueba tendría serias repercusiones y la persona que hizo el gran avance será una celebridad.

Nadie va a demostrar que [matemáticas] P = NP [/ matemáticas], porque simplemente no es cierto, pero si alguien debe hacerlo de todos modos, entonces depende mucho de la naturaleza de la prueba. Podría ser que la prueba establezca que estas dos clases de problemas deben ser las mismas, pero en realidad no proporciona mucha información sobre cómo se pueden resolver los problemas en NP en el tiempo polinómico. En ese caso, una gran parte del misterio permanecería, pero la gente comenzaría a trabajar muy duro para comprender cómo es posible que todos estos problemas aparentemente extremadamente difíciles (como el vendedor ambulante o el problema de la mochila) puedan ser fáciles después de todo. .

Finalmente, si la prueba realmente muestra cómo los problemas en NP pueden resolverse de manera eficiente, entonces de repente tenemos que repensar todo nuestro software de criptografía y se idearán muchos algoritmos nuevos para resolver todo tipo de problemas mucho más rápido que antes, con implicaciones que son … difíciles de predecir

Dependerá de lo nerd que quieras hacer. NP es para tiempo polinomial no determinista, y P es para tiempo polinomial. La pregunta se reduce a esto:

Si puedo verificar una solución en tiempo polinómico, ¿también puedo encontrar la solución en tiempo polinómico?

Sabemos que hay una clase de problemas realmente difíciles que siempre usamos cosas muy avanzadas, incluidas las computadoras para resolver. Pero no hemos demostrado que sean tan difíciles como pensamos, ni hemos demostrado que sean fáciles.

Es algo importante de resolver, pero depende de su perspectiva. La mayoría de los matemáticos y los informáticos creen que P no es igual a NP, lo que significaría negocios como de costumbre. Si P fuera igual a NP, los negocios no serían habituales en absoluto. Https, la criptografía y nuestra capacidad de predecir el caos se verían afectados. Nuestra información se volvería insegura y el estado de la tecnología humana mejoraría dramáticamente prácticamente de la noche a la mañana. Pero, eso no es tan probable.

Personalmente, no veo ninguna razón para creer que P es NP. Me encantaría que así fuera, pero habríamos visto alguna evidencia de esto. Lograr que la tecnología mejore seguirá siendo un viaje difícil y largo, como siempre ha sido. De acuerdo, hay ajustes y comienzos que hacen grandes cambios, pero … esta es una venta difícil.

Corea del Norte está demasiado ocupada tratando de demostrar
K = NK
(Corea = Corea del Norte).

Lo que sucedería es que romperían todas las formas de seguridad criptográfica como AES, DES, etc. y podrían espiar a prácticamente cualquier gobierno.

Serían capaces de acelerar el modelado científico complejo por un factor importante que resultaría si mutaciones peligrosas de la ciencia si no se controlan y regulan. La síntesis de proteínas, entre otras cosas, funciona en un algoritmo exponencial, y también lo hacen los modelos subatómicos.

Se acercarían un paso más al desarrollo de IA autoconsciente, que podría usarse para muchos ciberdelitos complejos a través de Internet.

Ah, y a Kim Jong Un, naturalmente, se le atribuiría el descubrimiento, y el científico que logró la hazaña probablemente sería enviado a un campo de trabajo para callarlo.

a corto plazo no pasa nada, porque la Academia establecida espera que la prueba sea -ve y provenga de sí mismos, por lo que pasa desapercibida. Luego, después de un tiempo, los estudiantes e ingenieros de repente saben cómo resolver problemas difíciles sin preocuparse por cómo se hace, refiriéndose solo a los algoritmos en la prueba difícil de leer. Cuando finalmente se reconoce la prueba (años después de su publicación) comienza una nueva era en la que las universidades pierden el liderazgo en CS y cada uno tiene su propia visión del mundo. Las grandes expectativas relacionadas con lo que sucede si el problema se resuelve positivamente se quedan cortas, ya que fueron exageraciones en primer lugar …

Siguiendo la definición de este artículo, y pensando lógicamente, estas son las conclusiones que podemos sacar:

En términos más simples, P representa problemas que son fáciles de resolver para las computadoras, y NP representa problemas que no son fáciles de resolver para las computadoras, pero que son fáciles de verificar.

P! = NP en la práctica, porque es ilógico que sea cierto. Solo en el mundo cuántico puede ser cierto.

Examinemos todos los casos.

Para que sea cierto, tenemos 3 casos aquí:

P = 0. Entonces tenemos 0 = 0 * N = 0 (P no es un problema real)

N = 1. Entonces P = P, eso significa que tenemos un problema sin solución sin una solución.

P&N = 1 al mismo tiempo, lo que significa que 1 = 1 * 1, lo que significa que el problema y la solución son la misma cosa. Esto es posible solo en el mundo cuántico, donde una partícula puede existir en dos estados al mismo tiempo. Como el gato de Schrodinger, que está vivo y muerto al mismo tiempo y no tiene ningún problema.

Aquí está la lógica:

La pregunta sigue abierta: ¿Son los problemas P y NP los mismos problemas? ¿O hay algunos problemas que se verifican fácilmente pero no se resuelven fácilmente?

Todos los problemas son únicos y sus soluciones pueden ser similares, pero no iguales. Pueden ser lo mismo si no tenemos un problema real (P = 0) o si no tenemos una solución al problema y es un problema sin solución (N = 1 y P = P entonces).

Si probamos “hechos de la vida”, es decir, problemas que ya se han resuelto, o problemas que simplemente no tienen solución, P = NP, pero en todos los demás casos, donde P! = 0 (nosotros tiene un problema real) o N! = 1 (es solucionable), o P y N no son iguales a 1 en cuyo caso tenemos una paradoja, porque un problema no puede ser el mismo que su solución (a menos que están en el mundo cuántico, donde una partícula puede estar en muchos estados al mismo tiempo), P nunca será igual a NP, y además de eso, ya que solo podemos saber que N = 1 (es decir, el problema no no tenemos una solución) si ya la hemos “resuelto” y comprobado con certeza que no tiene una solución, en cuyo caso ya no es un problema válido, y llegamos nuevamente al primer párrafo P = 0 (No tenemos un problema real).

TL; DR: Por ahora, esto será cierto solo para problemas, que en realidad no son problemas. Si lo alimenta un problema real, no puede ser cierto. Sin embargo, con las computadoras cuánticas, donde una partícula puede estar en dos estados al mismo tiempo, como el gato de Schrodinger, que está muerto y vivo en la caja, P y N estarán ambos = a 1 y este será su estado natural, y luego será factible. Hasta entonces, no lo es, al menos no en el mundo real.

– Si [math] P = NP [/ math] y la prueba es constructiva, podemos tener algunos problemas con pruebas de conocimiento cero. Todos se sorprenderían y muchos investigadores de CS perderían grandes apuestas. El mundo sigue exactamente de la misma manera que antes.
– Si [math] P = NP [/ math] y la prueba no es constructiva, algunos investigadores probablemente pasarían sus vidas buscando al menos un algoritmo P para un problema de NP. Algunas personas pierden apuestas, algunas personas discuten para salir de ellas. El mundo sigue exactamente de la misma manera que antes.
– Si [math] P \ ne NP [/ math], bueno, acabamos de confirmar lo que todos sabían. El mundo sigue exactamente de la misma manera que antes.

(EDITAR: no para minimizar la importancia matemática del problema P vs. NP, pero supongo que OP se refería a las repercusiones cotidianas de tal cosa)

Sudoku es np completo y parte del problema de coloración del gráfico.

Ciertamente, puede reducir la búsqueda de más soluciones considerando que x = ayb para cualquier valor entero positivo de x. para que pueda tomar un valor entero positivo de x y obtener a y b o decir que tiene los valores de a y b puede deducir x.

En este ejemplo usamos x = {a, b} = {1,1}, {1,2}, {2,1}, {1,3}, {2,2}, {3,1}, { 1,4}, {2,3}, {3,2}.

Esto significa que el problema de probar el cambio en una cuadrícula x es una cuestión de probar las cuadrículas ayb con los 9 colores establecidos en el número más resuelto primero y el número menos resuelto por último, por lo que es un problema reducido.

Esto junto con las posibles pruebas diagonales que hacen uso de la repetición de todas las otras configuraciones válidas de subcuadrícula 3 * 3 que se pueden resolver para reglas conocidas sobre las diagonales. Esto podría ayudar a resolver Sudoku mucho más cerca o en p tiempo.

incluso si tiene que probar números aleatorios, puede probar muchos números aleatorios del 1 al 9, pero extraídos de los datos ahora pesados ​​sobre qué es posible elegir los números / cuadrados menos probables y ver lo que ha resuelto después de probar un número si es una solución aparece el error Esto significaría que el cuadrado no es ese color, ya que prueba un solo cuadrado a la vez contra lo que puede deducir de las pruebas de datos anteriores. Si nada más resolver Sudoku es al menos un problema muy reducido en comparación con probar varios cuadrados al mismo tiempo, siempre que obtenga al menos una reducción antes de completar este proceso.

No puedo ver cómo esto no es un tiempo polinómico y P no determinista para algunos problemas o un enfoque de tiempo p completamente determinista, pero podría estar equivocado.

Lo que uno tiene que preguntar es si el proceso se atasca y no encuentra más soluciones para algunos diseños de sudoku con poca pista o al menos siempre encontrará una reducción una vez que se hayan realizado todas las comprobaciones.

Si estas comprobaciones no siempre resuelven este tipo de problema, entonces p puede terminar igualando np la mayor parte o parte del tiempo, pero si eso es cierto, p vs np solo podría resolverse parcialmente aquí o puede ser completamente p tiempo con menos hinchazón algorítmica o no todas las pruebas pueden ser necesarias incluso.

Bueno, todos sabrán que Sony encontró la prueba y que Corea del Norte simplemente pirateó sus sistemas y los “ganó”. En cuanto al mundo, solo invertirán toneladas de millones de dólares para proteger sus sistemas.

Eso es lo que se espera, por lo que no pasará nada, el mundo estará en paz y el científico / ingeniero podrá seguir viviendo felizmente con sus trabajos de rutina.

Solo el autor tendrá una vida mejor.

Estoy bastante seguro de que Kim Jong Un ya lo demostró.

Serían capaces de resolver muchos problemas difíciles, probablemente rompan muchos, pero no todos los criptosistemas (no estoy al tanto de un criptosistema de clave pública resistente a ese escenario), y tendríamos que recurrir a problemas NP-Hard que no son notario público

Que alguien ganará $ 1 millón.
Problemas del Premio del Milenio

Sería traducido a varios idiomas y publicado en las revistas.

Nadie sabría quién hizo la prueba, pero se conocerá como el teorema de Kim Jong Un, y todos los niños norcoreanos deben memorizar la prueba.

En un universo paralelo, ya han resuelto todos los problemas.
Ohh, no tenían computadoras

El Líder Supremo ya tiene todas las pruebas, simplemente no desea compartirlas.