Primero, reforzaré un punto crucial: nadie sabe si eso es cierto o no. Una resolución creíble para P vs NP ha eludido a los investigadores durante tanto tiempo como se hayan conocido las declaraciones adecuadas del problema.
Y no es que este sea un hito inactivo en la investigación de la complejidad computacional que tampoco recibe mucha atención: P vs NP impregna la informática como ninguna otra pregunta. Aparentemente, todas las vías de investigación en la teoría de la complejidad descubren (y luego, algo torpemente se abren camino) otro problema más relacionado con la resolución de P vs NP. Se encuentran problemas de NP completo en TI, ciencia, ingeniería, economía y otras áreas como el reloj. El escenario está preparado para que aparezca una respuesta y dramáticamente (re) moldee la cara de la informática tal como la conocemos. (Ah, y la investigación matemática, el desarrollo de software, la investigación científica …) Entonces, como se podría imaginar, el problema ha sido objeto de escrutinio por parte de miles de expertos, y los intentos de millones de otros para resolver los problemas NP-difíciles encontrados naturalmente probablemente cuentan aquí como bien. Y los teóricos han hecho un trabajo increíble de mapear el paisaje, de comprender la pregunta desde una variedad increíblemente diversa de perspectivas, muchas de las cuales emana este tentador “seguramente una respuesta es solo un paso trivial”, y, sin embargo, en gran parte todo P vs NP ha cedido a todo este escrutinio, ¡es casi una burla de comprensión de por qué nuestras técnicas más relevantes son inadecuadas para resolverlo!
Hay algo profundamente enigmático sobre la capacidad de recuperación de este problema frente a todo lo que hemos visto, y es por eso que enfatizo lo importante que es que aún no lo hayamos solucionado, incluso si podemos reírnos de la sugerencia del responde que es un “sí”. El sentido es que se necesitará una visión radicalmente nueva e innovadora para resolver este problema rigurosamente, y eso significa que el mundo en el que * sabemos * P no es igual a NP está separado del que vivimos. por una increíble fuente de poder explicativo. (¡Sin mencionar el peso bruto del poder explicativo al que tenemos acceso si P = NP!) Ese tipo de poder explicativo es el material de las revoluciones científicas y tecnológicas. El último avance de esta naturaleza básicamente nos dio computadoras.
Por lo tanto, el hecho de que aún no hayamos resuelto este problema es importante.
Mientras tanto, tenemos que conformarnos con nuestra mejor suposición sobre el asunto, y usted lo quería en “términos simples”. Para eso, solo voy a robar el punto 9 de uno de los viejos artículos de Scott Aaronson, porque simplemente lo clava:
“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 encuentra. Todos los que podrían apreciar una sinfonía serían Mozart; todos los que pudieran seguir un argumento paso a paso serían Gauss; todos los que pudieran reconocer una buena estrategia de inversión serían Warren Buffett. Es posible poner el punto en términos darwinianos: si esto es el tipo de universo que habitamos, ¿por qué no habríamos evolucionado para aprovecharlo?
Vale la pena leer el resto del artículo, pero en su mayor parte es un poco más técnico:
Razones para creer
