Sea S un problema NP-completo. Q y R son otros dos problemas que no se sabe que son NP. Q es el tiempo polinomial reducible a S y S es el tiempo polinomial reducible a R. ¿Cuál de las siguientes afirmaciones es verdadera?
(A) R es NP-completo
(B) R es NP-duro
(C) Q es NP-completo
(D) Q es NP-duro
Respuesta: (B)
Explicación: Consulte: GATE-CS-2006 | Pregunta 16
La opción (B) es correcta.
Cuestionario de esta pregunta
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