Se ha pedido a Ram y Shyam que demuestren que cierto problema Π es NP-completo. Ram muestra una reducción de tiempo polinomial del problema 3-SAT a Π, y Shyam muestra una reducción de tiempo polinomial de Π a 3-SAT. ¿Cuál de los siguientes se puede inferir de estas reducciones?
(A) Π es NP-duro pero no NP-completo
(B) Π está en NP, pero no es NP-completo
(C) Π es NP-completo
(D) Π no es NP-duro ni en NP
Respuesta: (C)
Explicación: dado que es posible la reducción del tiempo polinomial del problema 3-SAT a Π, es NP difícil.
Dado que es posible la reducción del tiempo polinomial de Π a 3-SAT, es NP-Completo.
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