Sea pA un problema que pertenece a la clase NP. Entonces, ¿cuál de las siguientes es VERDADERA?
(A) No existe un algoritmo de tiempo polinomial para pA
(B) Si pA se puede resolver de forma determinista en tiempo polinomial, entonces P = NP
(C) Si pA es NP-duro, entonces es NP-completo.
(D) pA puede ser indecidible.
Respuesta: (C)
Explicación:
Si un problema es tanto NP difícil como NP, entonces es NP Completo. Consulte https://www.geeksforgeeks.org/np-completeness-set-1/ para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA