¿Por qué NP = P es tan difícil de resolver?

Hay muchas evidencias de que el problema NP vs P es difícil de resolver. (Una de las mayores evidencias es: “Algunas personas muy brillantes lo han intentado y han fallado”: P)

Sin lugar a dudas, P vs NP es el problema abierto más importante en matemáticas y ciencias computacionales. La razón por la que es tan importante es porque captura la idea central de la computación: ” ¿Verificar una solución es fundamentalmente más fácil que encontrar la solución? ” Supongamos que dada una solución a un problema, puede verificar fácilmente si es correcta o no. Ahora, el problema P vs NP pregunta si existe un algoritmo rápido para encontrar dicha solución (o para informar que no existe dicho algoritmo). P vs NP pregunta, en esencia pregunta ” ¿Hay alguna manera de evitar la fuerza bruta mediante el uso de alguna técnica inteligente? ”

Es uno de los siete problemas del milenio de arcilla (como la hipótesis de Riemann, etc.) para los cuales una solución exige un premio de un millón de dólares. Pero, incluso entre esos siete, P vs NP tiene el escenario más especial de todos. Si alguien descubriera que P = NP y el algoritmo era eficiente en la práctica (y constructivo), entonces no solo podría resolver un problema del Milenio, sino también los siete. Solo necesita programar su computadora para buscar pruebas formales de los otros seis. (Para aquellos interesados, THEOREMS es un conocido problema de NP completo. Infórmese sobre esto en Wikipedia)

Los principales obstáculos para resolver el problema P vs NP es la falta de resultados de límite inferior . Los investigadores han probado muchos modelos computacionales (máquinas de Turing, circuitos booleanos, etc.), pero los fuertes resultados de límite inferior nos eluden en cada uno de estos modelos. Hasta ahora, ni siquiera estamos cerca de los límites inferiores que pueden resolver el problema P vs NP. La mayoría de las evidencias sugieren que P [math] \ neq [/ math] NP. Hay muchos otros obstáculos para probar los límites inferiores, como la relativización, la barrera de prueba natural, la algebrización, etc. (Puede obtener información sobre estos a partir de un texto estándar de Complejidad computacional).

Dato curioso: en una encuesta de matemáticos y científicos teóricos de la computación realizada por William Gasarch en 2002 , hubo 61 encuestados que dijeron que P no es igual a NP, pero también 9 que dijeron P = NP. (En una encuesta de seguimiento que Gasarch realizó en 2012, hubo 126 encuestados que dijeron que P no es igual a NP, y nuevamente 9 que dijeron P = NP.) Donald Knuth cree que P es igual a NP.

Apenas ha habido una abolladura en el problema P vs NP desde su introducción por Cook en la década de 1970. Nadie sabe de dónde podría venir el próximo gran avance.

Para mí, espero que alguien entre nosotros nos ilumine una solución al problema P vs NP y, por lo tanto, esta respuesta se vuelva obsoleta.

Primero, como otros han señalado: el consenso entre el campo es que P = / = NP, no P = NP.

Segundo: la teoría de la complejidad es un campo relativamente nuevo (en comparación con, por ejemplo, el álgebra abstracta), y los teóricos de la complejidad no han sido muy buenos para demostrar separaciones no triviales de clases de complejidad, por lo que no es tan sorprendente que aún no hayamos desarrollado La maquinaria para probar una de las separaciones más grandes.

No soy un experto en el área, por lo que esta podría no ser la mejor respuesta.
Pero una de las muchas dificultades para resolver (en lugar de resolver) el problema P vs NP es que no sabemos lo que estamos tratando de probar ([math] \ mathcal {P} = \ mathcal {NP} [/ math] o [matemática] \ matemática {P} \ neq \ matemática {NP} [/ matemática]).
Aunque el consenso de la comunidad parece ser que [math] \ mathcal {P} \ neq \ mathcal {NP} [/ math].