¿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 … Continue reading «Algoritmos | NP Completo | Pregunta 5»
El problema 3-SAT y 2-SAT son (A) ambos en P (B) ambos NP completos (C) NP-completos y en P respectivamente (D) indecidibles y NP-completos respectivamente Respuesta: (C) Explicación: El problema booleano de satisfacibilidad (SAT) es un problema de decisión, cuya instancia es una expresión booleana escrita usando solo AND, OR, NOT, variables y paréntesis. El … Continue reading «Algoritmos | NP Completo | Pregunta 4»
Sean S un problema NP-completo y Q y R otros dos problemas que no se sabe que están en NP. Q es el tiempo polinomial reducible a S y S es el tiempo polinomial reducible a R. ¿Cuál de las siguientes afirmaciones es verdadera? (GATE CS 2006) (A) R es NP-completo (B) R es NP-duro … Continue reading «Algoritmos | NP Completo | Pregunta 2»
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 … Continue reading «Algoritmos | NP Completo | Pregunta 3»
¿Cuál de los siguientes es cierto acerca de los problemas NP-Complete y NP-Hard? (A) Si queremos demostrar que un problema X es NP-Difícil, tomamos un problema NP-Difícil conocido Y y lo reducimos a X (B ) El primer problema que se demostró como NP-completo fue el problema de satisfacibilidad del circuito. (C) NP-completo es un … Continue reading «Algoritmos | NP Completo | Pregunta 6»