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

Answer 1

En realidad, para agregar una palabra de precaución a estas respuestas diciendo que P = NP significaría que el cifrado de clave pública es inseguro, y todos los problemas famosos con pruebas cortas se probarían rápidamente, en realidad eso no se sigue en absoluto.

El tiempo polinomial no te dice nada sobre los coeficientes del polinomio. ¿Qué sucede si los coeficientes son todos del orden de 10 ^ (10 ^ 10) (1 seguido de 10,000,000,000 ceros) o más?

Incluso una solución en tiempo lineal no tendría ningún uso práctico si el coeficiente es enorme.

Para poner un ejemplo, supongamos que alguien encuentra una solución al problema del vendedor ambulante que requiere como máximo 10 ^ (10 ^ 10) * n pasos, donde n es el número de ciudades?

Esa es una solución de tiempo lineal, y si alguien encontrara una solución de este tipo, probaría P = NP, (porque es un problema completo de NP), serían inmediatamente famosos, pero no es una solución práctica.

No sería para nada sorprendente si apareciera con coeficientes realmente enormes como ese. Tal vez incluso los coeficientes que necesitan la notación de flecha hacia arriba de Knuth (de manera similar al número de Graham). Entonces todavía sería un resultado teóricamente muy interesante, incluso si los coeficientes son demasiado grandes para ser expresados ​​con notación exponencial.

Por supuesto, muchos matemáticos trabajarían en la prueba para tratar de reducir el tamaño de los coeficientes, pero no hay una razón a priori por la que tengan que reducirlos en la medida en que sea prácticamente útil.

Answer 2

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, al igual que el modelado subatómico.

Se acercarían un paso más al desarrollo de IA consciente de sí mismo, que podría usarse para muchos delitos cibernéticos complejos a través de Internet.

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

Answer 3

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 una 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 depender de mecanismos que no estén basados ​​en estándares (algoritmos no publicados) o de 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 polinómico real para problemas NP-Hard. Sin embargo, la prueba en sí misma podría conducir a ideas que podrían ser útiles.

Answer 4

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 simple 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. La ventaja probablemente sería la ingeniería inversa rápidamente, o ser tomada 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 sea que 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 al problema de Travelling Saleman (que tiene muchas aplicaciones prácticas).

Answer 5

(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.

Answer 6

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 rodea a las personas que lo probaron , 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 debería 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 se pueden resolver 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

Answer 7

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 sea 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.

Answer 8

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 …

Answer 9

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 iguales 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 serán ambos = 1 y este será su estado natural, y luego será factible. Hasta entonces, no lo es, al menos no en el mundo real.

Answer 10

– 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 [matemática] P = NP [/ matemática] 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 [matemática] P \ ne NP [/ matemática], 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)

Answer 11

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 de cuadrícula de 3 * 3 válidas 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 verificaciones.

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.

Answer 12

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.

Answer 13

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

Solo el autor tendrá una vida mejor.

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

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.

Answer 19

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

Answer 20

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