Considere los siguientes dos problemas en grafos no dirigidos
α : Given G(V, E), does G have an independent set of size | V | - 4? β : Given G(V, E), does G have an independent set of size 5?
¿Cuál de las siguientes es VERDADERA?
(A) α está en P y β es NP-completo
(B) α es NP-completo y β está en P
(C) Tanto α como β son NP-completos
(D) Tanto α como β están en P
Respuesta: ( C)
Explicación: El problema de decisión de un conjunto independiente de gráficas 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