Si está tan claro que P! = NP, ¿por qué nadie se las ha arreglado para probarlo? Aprendiendo y Estudiando para siempre

En primer lugar, no es tan claro como se piensa. Si bien definitivamente es la opinión predominante que P! = NP, no es como si cada uno de los expertos estuviera de acuerdo: según una encuesta https://www.cs.umd.edu/~gasarch/…

61 respondieron ellos piensan que P! = NP
9 respondieron ellos piensan que P = NP
4 pensaron que es independiente de los axiomas [tenga en cuenta que si bien se podría argumentar que, desde una perspectiva práctica, no se puede distinguir del veredicto P! = NP, las posibles técnicas de prueba serían completamente diferentes si esta es la tesis que debe probarse]

(…) Otro

22 no ofreció opinión

Estas estadísticas indican (como es lógico) que entre los que respondieron la mayoría pensaron que P! = NP. La mayoría de los 9 que pensaron que P = NP eran miembros respetables de la comunidad. Todos ellos reconocieron que su opinión es un punto de vista minoritario. Algunos incluso dijeron que lo tomaron solo por el contrario. Sin embargo, el hecho de que 22 personas no se hayan aventurado a emitir una opinión indica más incertidumbre sobre esto de lo que uno hubiera pensado.

¿Pero a partir de por qué esto ha resultado ser tan difícil de probar? Bueno, no creo que se pueda dar una razón estricta sobre la cual todos estén de acuerdo y, si la hay, no estoy en posición de saberlo, pero parece que la idea de probar la no existencia de un algoritmo haciendo algo no es lo que Uno ve claramente cómo acercarse. Por supuesto, en matemáticas tenemos una carga enorme de pruebas muy fáciles para la no existencia de las cosas, pero por lo general son pruebas por contradicción, lo que significa que para realizar una necesitamos encontrar algo que nuestra hipótesis resulte contraria. No es tan fácil pensar en algo contrario a la idea de la existencia de un algoritmo que hace algo, y por lo tanto, las pruebas en la teoría de la complejidad suelen ser reducciones: es fácil probar la contradicción si uno asume que algún problema es difícil, entonces podemos reducir otros. Problema y encontrar una contradicción con la hipótesis de que este otro problema es fácil. Probar P! = NP parece requerir un tipo de contradicción que no relaciona un problema con otro, sino una contradicción con la suposición de cuán efectivo puede ser el cálculo del problema. Podemos tener una intuición bastante buena (¿o tal vez mala?) De que “un problema dado en tales términos no puede resolverse mejor que la idea que hace uso ingenuo de estos términos” [tenga en cuenta que parece haber ejemplos mucho más obvios de esto que NP, por ejemplo, de los menos conocidos. La clase de PPAD viene a la mente: esto realmente no puede ser posible resolver un problema de esta clase más rápido que ingenuamente, como, incluso, no hay espacio para pensar en otras posibilidades para abordar un problema con tal conocimiento limitado, ¿verdad? – pero bueno, no hay pruebas de dureza], pero tratando de encontrar una verdad específica del universo [bueno, quiero decir, verdad del sistema de axiomas …] que se violaría resolviéndolo más rápido que “intuitivamente obvio”. Esto no parece una tarea obvia O al menos esto puede ser lo que podría dar como mi intuición no lo suficientemente bien informada.