Un problema en NP es NP-completo si
(A) Se puede reducir al problema 3-SAT en tiempo polinómico
(B) El problema 3-SAT se puede reducir a él en tiempo polinomial
(C) Se puede reducir a cualquier otro problema en NP en tiempo polinomial
(D) ) algún problema en NP se puede reducir a él en tiempo polinomial
Respuesta: (B)
Explicación: Un problema en NP se convierte en NPC si todos los problemas NP se pueden reducir a él en tiempo polinomial. Esto es lo mismo que reducir cualquiera de los problemas de NPC. 3-SAT siendo un problema de NPC, reducirlo a un problema de NP significaría que el problema de NP es NPC.
Consulte: https://www.geeksforgeeks.org/np-completeness-set-1/
Prueba de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior
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