Assuming P != NP, which of the following is true ? (A) NP-complete = NP (B) NP-completeP =
(C) NP-hard = NP (D) P = NP-complete
(A) A
(B) B
(C) C
(D) D
Respuesta: (B)
Explicación:
La respuesta es B (ningún problema NP-Completo se puede resolver en tiempo polinomial). Porque, si un problema NP-Completo se puede resolver en tiempo polinomial, entonces todos los problemas NP se pueden resolver en tiempo polinomial. Si ese es el caso, entonces NP y P se vuelven iguales, lo que contradice la condición dada.
Artículo relacionado:
NP-Completitud | Conjunto 1 (Introducción)
Problema P versus NP (Wikipedia)
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