Supongamos que se descubre un algoritmo de tiempo polinomial que calcula correctamente la camarilla más grande en un gráfico dado. En este escenario, ¿cuál de los siguientes representa el diagrama de Venn correcto de las clases de complejidad P, NP y NP Completa (NPC)?
(A) A
(B) B
(C) C
(D) D
Respuesta: (D)
Explicación: Clique es un problema NP completo. Si un problema NP completo se puede resolver en tiempo polinomial, entonces todos se pueden resolver. Entonces el conjunto de NPC se vuelve igual a P.
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