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 … Continue reading «Algoritmos | NP Completo | Pregunta 5»

Implementación del problema del viajante de comercio (TSP)

Problema del viajante de comercio (TSP): dado un conjunto de ciudades y distancias entre cada par de ciudades, el problema es encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y regrese al punto de partida. Tenga en cuenta la diferencia entre el ciclo hamiltoniano y TSP. El problema del ciclo hamiltoniano … Continue reading «Implementación del problema del viajante de comercio (TSP)»

Algoritmos | NP Completo | Pregunta 4

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»

Prueba de que el problema de decisión de camarilla es NP-Completo

Requisito previo: NP-Completitud Una camarilla es un subgrafo de un grafo tal que todos los vértices en este subgrafo están conectados entre sí, es decir, el subgrafo es un grafo completo. El problema de la camarilla máxima es encontrar la camarilla de tamaño máximo de un gráfico G dado, que es un gráfico completo que … Continue reading «Prueba de que el problema de decisión de camarilla es NP-Completo»

Algoritmos | NP Completo | Pregunta 2

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»

Prueba de que el ciclo hamiltoniano es NP-Completo

Requisito previo: NP-Completitud , ciclo hamiltoniano . Ciclo hamiltoniano: un ciclo en un gráfico no dirigido G = (V, E) que atraviesa cada vértice exactamente una vez. Declaración del problema: dado un gráfico G (V, E), el problema es determinar si el gráfico contiene un ciclo hamiltoniano que consta de todos los vértices que pertenecen … Continue reading «Prueba de que el ciclo hamiltoniano es NP-Completo»

Algoritmos | NP Completo | Pregunta 3

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»

3 colores es NP completo

Prerrequisito: NP-Completo , coloreado de gráficos Problema de coloración K de gráficos : un problema de coloración K para gráficos no dirigidos es una asignación de colores a los Nodes del gráfico de modo que no haya dos vértices adyacentes que tengan el mismo color, y como máximo se utilizan K colores para completar el … Continue reading «3 colores es NP completo»

Algoritmos | NP Completo | Pregunta 6

¿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»

El problema del conjunto de golpes es NP completo

Prerrequisito: NP Completo Problema : dado un conjunto base X de elementos y también una colección de agrupación C de subconjuntos disponibles en X y un número entero k , la tarea es encontrar el subconjunto más pequeño de X , tal que el subconjunto más pequeño, H ,coincida con todos los conjuntos comprendidos en … Continue reading «El problema del conjunto de golpes es NP completo»