Algoritmos | NP Completo | Pregunta 5

¿Cuáles de las siguientes afirmaciones son VERDADERAS?
(1) El problema de determinar si existe un ciclo en un grafo no dirigido está en P.
(2) El problema de determinar si existe un ciclo en un grafo no dirigido está en NP.
(3) Si un problema A es NP-Completo, existe un algoritmo de tiempo polinomial no determinista para resolver A.
(A) 1, 2 y 3
(B) 1 y 3
(C) 2 y 3
(D) 1 y 2

Respuesta: (A)
Explicación: 1 es verdadero porque la detección de ciclos se puede realizar en tiempo polinomial usando DFS (ver esto ).
2 es cierto porque P es un subconjunto de NP.
3es cierto porque NP completo también es un subconjunto de NP y NP significa que existe una solución de tiempo polinomial no determinista . (Ver esto ) Cuestionario de esta pregunta