¿Qué pasaría si probara P = NP?

Una mera prueba de P = NP no haría mucho por sí misma. Lo interesante sería un algoritmo rápido para resolver problemas NP-hard. Lo que sucedería entonces dependerá de qué tan rápido sea el algoritmo. Supongamos un polinomio de bajo grado con coeficientes manejables.

Un algoritmo de tiempo lineal o cuadrático para SAT rompería prácticamente todas las criptomonedas, excepto el pad de una sola vez. La comunicación de Internet sería insegura a menos que las partes compartieran datos de OTP. Probablemente valdría la pena que los bancos repartieran tokens OTP, pero en general la situación de seguridad sería bastante terrible. Algunos protocolos podrían intentar buscar con un margen de seguridad cuadrático, pero estos solo serían útiles para la seguridad a corto plazo.

Por otro lado, un algoritmo rápido para SAT revolucionaría el resto del mundo. De repente, muchos problemas en la IA se volverían fáciles. El diseño asistido por computadora se volvería mucho más poderoso, ya que las computadoras podrían encontrar rápidamente el diseño óptimo para casi cualquier cosa.

En general, un P = NP efectivo sería bueno para el mundo, no está mal.

Si su prueba resiste el riguroso escrutinio al que (eventualmente) será sometida, sucederá lo siguiente.

Lo que te sucederá:

Serás el brindis de la ciencia popular. Recolectará su premio en metálico de un millón de dólares (menos impuestos), nunca querrá empleo ni otorgará dinero nunca más. Gane una gran cantidad de premios, entre los que se incluyen el premio Turing, el premio Nevanlinna, el premio Gödel e incluso, posiblemente, la medalla Fields.

Qué pasará con tu trabajo:

Será analizado por teóricos de la complejidad en todas partes y los conocimientos que utilice para demostrar su resultado conducirán a varios avances en el campo en los próximos años. La mayoría de las conferencias teóricas, incluidas STOC y FOCS, se inundarán de documentos en la nueva área que generará, y muy rápidamente habrá una conferencia / taller dedicado en la nueva área de complejidad que comenzará. Muchos profesores y jóvenes estudiantes de posgrado aprovecharán su éxito y secarán esta área.

Tenga en cuenta que esto solo son las técnicas que emanan de su resultado. Su resultado en sí mismo no conducirá a demasiados avances científicos. La mayoría de los teóricos de la complejidad ya trabajan con el supuesto de que P no es igual a NP. Es solo que se actualizarán muchos documentos con declaraciones condicionales, lo que le dará un montón de citas en el proceso.

Lo que sucederá en el mundo en general:
La gente leerá sobre usted en los periódicos y volverá a trabajar enviando correos electrónicos encriptados y transfiriendo fondos en línea.

Nada al principio.

Una vez que publique su prueba, y otras personas la vean y vean que es correcta, le felicitarán, le darán premios, harán que los periodistas llamen y probablemente podría conseguir un trabajo en el departamento de informática de la universidad de su elección.

Muchas aplicaciones de la informática se construyen con el supuesto de que P no es igual a NP. Por lo tanto, una prueba de esta afirmación solo nos aseguraría aún más. Por otro lado, si demuestra que P = NP, entonces tendríamos que buscar nuevas formas de encriptar los datos para fines de transmisión (RSA supone que ningún algoritmo con complejidad P puede factorizar números). Además, la gente saldría a buscar un algoritmo para resolver problemas de tipo NP que podrían tener resultados sorprendentes en la medicina y muchas otras aplicaciones. Básicamente, cada problema que se resuelve mediante prueba y error se resolvería de manera eficiente mediante un algoritmo.

Por Scott Aaronson

Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que generalmente suponemos. No habría ningún valor especial en los “saltos creativos”, no habría una brecha fundamental entre resolver un problema y reconocer la solución una vez que se encuentre. Todos los que pudieran apreciar una sinfonía serían Mozart; todos los que pudieran seguir un argumento paso a paso serían Gauss; todos los que puedan reconocer una buena estrategia de inversión serían Warren Buffett. Es posible poner el punto en términos darwinianos: si este es el tipo de universo que habitamos, ¿por qué no habríamos evolucionado para aprovecharlo?

es mejor que tu prueba no sea:

Es suficiente mostrar N! = 1.

N = 14. Por lo tanto, N! = 1.

Esta prueba se aplica en cualquier lugar donde se use el alfabeto latino básico iso.

Resulta que la prueba es a menudo donde un principiante avanzado comienza su viaje en el campo de la investigación matemática en informática.

Bromeo

Cualquiera de los dos resultados, una prueba de que P = NP o de P ≠ NP , sería un triunfo para la persona que lo demuestra.

Probablemente no significaría mucho prácticamente a menos que el tiempo en que los algoritmos tuvieran un tiempo polinómico de bajo grado. Si se ejecutan en [math] \ mathcal O (n ^ {100}), [/ math] es tan lento que prácticamente no son mejores que el tiempo exponencial. Por otro lado, si se ejecutan en tiempo [matemático] \ matemático O (n ^ 3) [/ matemático], eso sería prácticamente significativo.

No mucho. Esa ha sido la suposición general durante décadas. Significa que hay algunos problemas que no se pueden resolver por completo de manera más eficiente que enumerar todas las respuestas posibles y verificarlas.

Lo contrario, por el contrario, sugeriría que los problemas de optimización tienen una solución directa. En ese caso, tendríamos muchos problemas con soluciones muy interesantes que aún no hemos descubierto. También rompería cualquier sistema que se base en la dificultad de resolver ciertos problemas.

Serías el # 108.

Página P-versus-NP.

Supongamos que está garabateado en una servilleta con lápices de colores, se arrojará a la basura, junto con todas las pruebas de que P = NP enviado por otras manivelas y chiflados. Si realmente tuviera pruebas de que P ≠ NP, probablemente no tendría que preguntar qué pasaría 🙂

… y el Premio Abel

Absolutamente, destruirá la base de cantidades de diferentes temas. Muchos documentos se convertirán solo en documentos.

¿Criptografía? ¿Aprendizaje automático?

Jesús, olvídalo.

La única forma de asegurar la información es una seguridad física realmente buena. Esto hace que los bancos quiebren, por ejemplo.