¿Crees que P = NP o no? ¿Por qué?

En su blog, Scott Aaronson da varias razones de por qué P! = NP es el caso más probable (Razones para creer). Encuentro lo siguiente particularmente interesante:

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?

Agregando también mis propios dos centavos sobre el tema, si observamos problemas no triviales en P (por ejemplo, 2SAT), vemos que todos los algoritmos de tiempo polinómico explotan la estructura combinatoria de los problemas de alguna manera, por lo que sería lógico decir que si continuamente hacemos que el problema sea más general y eliminemos toda la estructura, llegaríamos a los problemas más difíciles en NP que solo se pueden resolver probando todas las soluciones posibles.

No solo pienso que P = NP. Sé P = NP porque todas las máquinas, incluso las conceptuales, están acotadas. Esa no es la pregunta correcta, la pregunta correcta es: “¿Existe un algoritmo de tiempo polinómico eficiente para problemas de NP completo?” Yo no sé. Sospecho que la respuesta es sí. De lo contrario, debe explicar por qué un algoritmo de tiempo polinómico dado es el más pequeño posible que se puede asignar a problemas de NP completo.

( Nota : Tengo que publicar como Anónimo, porque ningún investigador serio sin antigüedad significativa, por lo menos la tenencia, puede pensar que P = NP. La Academia está rota, pero esa es otra pregunta. Espero que mi publicación sea rechazada por cada investigador “serio” que lee esto, porque no pueden manejar a nadie que desafíe sus creencias).

Usted ha escuchado a otras personas responder respuestas como “nadie ha encontrado una solución de tiempo polinomial para un problema NP-completamente, por lo tanto, no debe existir”.

Esta es una lógica absolutamente horrible y es vergonzoso que tantos informáticos y matemáticos la usen. Hacen esto para ahuyentar a los estudiantes (incluso si no se dan cuenta de que es por eso que lo están haciendo porque simplemente están repitiendo a otros en su campo), porque saben que es un problema realmente difícil y no quieren estudiantes que pierden su tiempo, cuando hay muchas más cosas útiles que hacer con computadoras y algoritmos. Eso y, por supuesto, no quieren ser recogidos. Numerosos profesionales pasan toda su carrera tratando de resolver el problema, y ​​algunos estudiantes de posgrado entran y lo hacen parecer trivial. Eso sería una gran vergüenza que quieren evitar a toda costa. Por último, si uno encontrara tal prueba (con bajos coeficientes polinómicos), esencialmente sería un “dios” entre los hombres. El poder de tal prueba está más allá de la comprensión si se aplica correctamente.

Ahora (como se mencionó anteriormente), la verdad es que el problema es trivial y P = NP porque todas las máquinas (incluso conceptuales) están limitadas. Pero, por supuesto, los matemáticos no aceptarán esta respuesta (porque son tercos), quieren saber si existe una respuesta de tiempo polinomial relativamente eficiente. No sé si existen coeficientes polinómicos bajos. Tal vez. Tal vez no. Estoy realmente indeciso. Pero solo para desafiar el status quo, no compro el argumento en mi primer párrafo simplemente porque hay muchos algoritmos y las personas están descubriendo nuevas ideas simples todo el tiempo en matemáticas. Si ni siquiera podemos enumerar las ideas simples, ¿qué nos hace pensar que hemos agotado todos o incluso una pequeña fracción de los algoritmos más complejos? Demonios, probablemente exista un algoritmo no tan complejo para la conciencia. Entonces, si eso está en el espacio de los algoritmos, diría que tenemos mucho más por recorrer antes de poder declarar que incluso hemos arañado la superficie del espacio de algoritmos que uno podría probar.

Por último, si observa el tiempo de ejecución de los algoritmos de aproximación y la calidad, nuestros algoritmos continúan mejorando. Si no hay límite (es decir, si la calidad se acerca al 100%) en la mejora, entonces P = NP. Si hay un límite (menos del 100%), ciertamente aún no lo hemos abordado, por lo que al menos no podemos decir que no existe un algoritmo de tiempo polinómico. En algún momento, cuando lleguemos a 99.999… 9% de calidad, simplemente podemos decir que no importa porque a todos los efectos prácticos tenemos una aproximación de calidad suficientemente buena.

Ese es mi tono. Si eres REALMENTE inteligente, y sabes que eres inteligente, y estás dispuesto a pasar tiempo aprendiendo la complejidad computacional y otras matemáticas relacionadas, entonces podrás demostrarlo de una forma u otra.

Como otros han mencionado, parece poco probable que P = NP, porque los problemas de NP completo se están trabajando muy extensamente durante mucho tiempo.

Pero si se demuestra que P = NP, entonces todo el infierno se desatará, porque todos los criptosistemas se volverán inseguros. Por lo tanto, no tendrá Internet seguro, ni banca segura, ni conexiones móviles seguras, ¡y así sucesivamente!

No estoy seguro de si P = NP o no, tomaría más una posición agnóstica.

Realmente no entiendo el fuerte sesgo en contra de creer que P = NP o que P podría ser igual a NP.

También estoy en desacuerdo con muchas analogías y argumentos utilizados por Scott Aaronson. Por ejemplo, dice “Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que normalmente 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 puedan apreciar una sinfonía serán Mozart; todos los que puedan seguir un argumento paso a paso serán Gauss “.

Pero esto no es cierto, ya se sabe que todos los problemas de NP completo tienen soluciones de tiempo exponencial. Algunos incluso tienen soluciones de tiempo pseudo-polinomiales.

Entonces, sin saber si P = NP o no, ya podemos decir que no hay un valor especial en los “saltos creativos”, que todos pueden ser Mozart y que todos los que puedan seguir un argumento paso a paso podrían ser Gauss.

La razón principal por la cual el problema P vs. NP es un gran problema es porque algunas cosas pueden tomar miles de años o más para computar. Básicamente es un problema de optimización o velocidad. También hay problemas en P que pueden tomar mucho tiempo para computar también.

Una solución de tiempo polinomial no es necesariamente la más rápida ni la más eficiente. Un ejemplo de esto se puede ver con las pruebas de primalidad. La división de prueba es más rápida en la mayoría de los casos que la prueba de primitividad de AKS, aunque la división de prueba es pseudopolinomial, mientras que la prueba de primigenia de AKS es polinomial.

Entonces, en muchas condiciones, no importará incluso si alguien encuentra una solución de tiempo polinomial a un problema debido a la existencia de algoritmos de tiempo pseudo-polinomiales para muchos problemas (y otras técnicas para hacer que las cosas funcionen más rápido) y también debido a un tiempo polinómico La solución no será necesariamente rápida o eficiente.

El argumento principal utilizado para creer que “P! = NP” es el hecho de que nadie ha encontrado una solución de tiempo polinomial para cualquier problema de NP completo, pero alguien también puede usar este mismo tipo de razonamiento sobre por qué “P = NP” , pueden argumentar que de todos los miles de problemas de NP completo, nadie ha mostrado una solución de tiempo polinomial como imposible.

Puede parecer a la mayoría que P! = NP, pero no estoy tan seguro.

Si nos fijamos en la historia, muchas conjeturas de hace cientos de años (antes del problema P vs. NP) aún no se han resuelto.

Hay varias formas de probar que P = NP. Simplemente se puede resolver uno de los miles de problemas NP-Complete o alcanzar mejores aproximaciones de algunos problemas, por ejemplo. El hecho de que nadie haya probado P = NP, a pesar de que hay tantas formas de hacerlo, parece que es más probable que P! = NP.

Pero podría haber respondido de manera diferente: hay varias formas de probar que P! = NP … El hecho de que nadie haya probado P! = NP hace que parezca más probable que P = NP.

Entonces, mi punto es que, cuando alguien está trabajando para demostrar que P = NP al resolver uno de los varios problemas de NPC, también está trabajando para demostrar que P! = NP al mostrar que el problema de NPC no se puede resolver en tiempo polinómico. Por ejemplo, nadie ha resuelto SAT (tiempo polinomial) pero nadie ha demostrado que SAT no puede resolverse (tiempo polinomial).

Así que solo quería mostrar que tenemos muchas posibilidades de mostrar que P! = NP y aún no lo hemos hecho (todavía).

Pero también creo que P! = NP (no porque sea más ‘probable’, sino porque tiene sentido que algunos problemas sean más difíciles que otros)

Si P = NP fuera cierto, significaría que durante años y años y años, nadie, de todos los miles de personas que trabajan en problemas difíciles de NP, pudo encontrar algoritmos para resolver estos problemas de manera eficiente, a pesar de que existen. Eso parece dolorosamente improbable.

Si se demostrara que es cierto, tendría que haber un salto sin precedentes en nuestra comprensión de los algoritmos. Simplemente no tiene sentido. P! = NP

Puede verificar la verdad en tiempo polinómico …… Pero no puede decidir cuál es la verdad … DIOS sabe la verdad y usted tiene que reducirse a ella para saber la verdad de cada cosa … (Problema NP) … Posible (P = NP) ???
Por lo tanto, si P = NP, entonces un día puede convertirse en DIOS … Y no creo que sea posible ……