Para los problemas X e Y, Y es NP-completo y X se reduce a Y en tiempo polinomial. ¿Cual de los siguientes es verdadero?
(A) Si X se puede resolver en tiempo polinomial, entonces también se puede resolver Y
(B) X es NP-completo
(C) X es NP-difícil
(D) X está en NP, pero no necesariamente NP-completo
Respuesta: (D )
Explicación:
Esta solución es aportada por Pranjul Ahuja .
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