Sea X un problema que pertenece a la clase NP. Entonces, ¿cuál de las siguientes es VERDADERA?
(A) No existe un algoritmo de tiempo polinomial para X.
(B) Si X se puede resolver de forma determinista en tiempo polinomial, entonces P = NP.
(C) Si X es NP-duro, entonces es NP-completo.
(D) X puede ser indecidible.
Respuesta: (C)
Explicación: (A) es incorrecta porque el conjunto NP incluye tanto P (polinomio soluble en tiempo) como NP-Completo.
(B) es incorrecta porque X puede pertenecer a P (la misma razón que (A))
(C) es correcta porque el conjunto NP-Completo es la intersección de los conjuntos NP y NP-Hard.
(D) es incorrecta porque todos los problemas NP son decidibles en un conjunto finito de operaciones.
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