Algoritmos | NP Completo | Pregunta 1

Suponiendo que P != NP, ¿cuál de las siguientes es verdadera?

(A) NP-completo = NP

(B) NP-completo P =

(C) NP-duro = NP

(D) P = NP-completo
(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.

Cuestionario de esta pregunta