¿Por qué si tenemos una reducción en el tiempo polinomial de un problema de P a un problema de NP, esto no muestra que P = NP (pero al contrario)?

Una reducción del problema A al problema B significa que si le dan un algoritmo mágico que resuelve el problema B, puede usar este algoritmo mágico como una caja negra para resolver el problema A. El tiempo adicional que necesitaría para hacerlo es el tiempo para haciendo la reducción (que en este caso es tiempo polinomial). Tal reducción nos dice que si puede resolver el problema B en tiempo polinómico, entonces también puede resolver A en tiempo polinómico (es decir, A no es más difícil que B si desconta el tiempo polinómico tomado para la reducción)

Ahora, una reducción del tiempo polinómico de un problema en P a un problema en NP significa que los problemas en P no son más difíciles que los problemas en NP. Sin embargo, esto no implica que podamos resolver el problema de NP en tiempo polinómico. Solo dice que si pudiéramos haber resuelto el problema NP (al que redujimos nuestro problema P) en tiempo polinómico, también podríamos resolver nuestro problema P en tiempo polinómico. Esta es una declaración redundante porque ya sabíamos, por definición, que nuestro problema P se puede resolver en tiempo polinómico. Por lo tanto, esta dirección de reducción es bastante inútil. La otra dirección, concretamente la de reducir un problema de NP a un problema de P, sería extremadamente significativa.

Un problema NP es aquel en el que puede proporcionar algún tipo de prueba de que la respuesta es correcta, que puede verificarse en tiempo polinómico. Eso es lo que significa NP. (Por ejemplo, resolver Sudoku es NP, porque puedes mostrarme la solución y puedo verificar que es correcta en tiempo polinómico).

Dado que cualquier solución a un problema en P se puede verificar en tiempo polinómico simplemente resolviéndolo de nuevo, esto significa que

Todos los problemas de P son NP.

Entonces, “la reducción del tiempo polinomial de un problema P a un problema NP” es bastante trivial, y no prueba nada muy interesante.

Ya sabemos que P es un subconjunto de NP. Probar lo contrario es lo difícil.

Todos los problemas de P son NP.

P = Problemas solucionables en tiempo polinómico por una máquina determinista
NP = Problemas solucionables por una máquina no determinista