Si P = NP, ¿significa que P=NP-Completo?

Question

Acabo de empezar a aprender sobre P vs Np y tengo una comprensión básica de P, NP y NP completo. Sólo quería una pequeña aclaración sobre cómo cada uno interactúa con los demás. Dado que NP-Completo está en NP, ¿significa eso que si P es igual a NP, los problemas que son NP-Completo también serían resolubles en tiempo polinomial? ¿O P también tendría que ser igual a NP-Duro para que NP-Completo fuera solucionable en tiempo polinomial?

Answer 1

Cada NP -problema completo es también un NP problema, por definición. Por lo tanto, si NP=P lo mismo ocurrirá con NP -problemas completos.

No se puede decir lo mismo de NP -problemas difíciles. Estos problemas incluyen todos los problemas más difíciles que NP problemas, excepto el NP -problemas completos. En este caso, tenemos que NP -duro $\cap $ NP \= NP -completa. Por lo tanto, incluso si NP \= P , seguiremos teniendo NP -duro $\neq$ P .

Esta imagen puede ayudarte a entender cómo interactúan estos conceptos.