Problema : dados 3 puntos a , b , c , la tarea es verificar si estos tres puntos son colineales. Explicación : una instancia del problema es una entrada especificada para el problema. Una instancia del problema de colinealidad son tres puntos ((ax , a y ), (b x , b y ), (c … Continue reading «Prueba de que el problema de colinealidad es NP completo»
Problema de isomorfismo de subgrafos : Tenemos dos grafos no dirigidos G 1 y G 2 . El problema es comprobar si G 1 es isomorfo a un subgrafo de G 2 . Isomorfismo de grafos: dos grafos A y B son isomorfos entre sí si tienen el mismo número de vértices y aristas, y … Continue reading «Prueba de que el problema de isomorfismo de subgrafo es NP-Completo»
Declaración del problema : dada una fórmula f , el problema es determinar si f tiene dos asignaciones satisfactorias. Explicación : una instancia del problema es una entrada especificada para el problema. Una instancia del problema Double Sat es una fórmula booleana f . Dado que un problema NP-completo es un problema que es tanto … Continue reading «Doble SAT es NP Completo»
Prerrequisito: Conjunto Dominante de un Gráfico , NP-Completo Un conjunto dominante en un grafo G = (V, E) es un subconjunto de vértices V’ siguiendo la condición de que los vértices que no pertenecen a V’ sean adyacentes a algún vértice en V’ . Problema: Dado un grafo G(V, E) y un entero k, el … Continue reading «Prueba de que el conjunto dominante de un gráfico es NP-completo»
Problema de igualdad de subconjuntos : Dado un conjunto S de valores enteros no negativos, el problema es identificar si hay una partición del conjunto S en dos conjuntos X e Y , tal que la suma de enteros en X es igual a la suma de enterosen Y. Explicación : una instancia del problema … Continue reading «La igualdad de subconjuntos es NP completa»
Problema 4-SAT : 4-SAT es una generalización de 3-SAT (k-SAT es SAT donde cada cláusula tiene k o menos literales). Declaración del problema : dada una fórmula f en forma normal conjuntiva (CNF) compuesta de cláusulas, cada una de cuatro literales, el problema es identificar si existe una asignación satisfactoria para la fórmula f . … Continue reading «Prueba de que 4 SAT es NP completo»
Requisito previo : Completitud de NP, Clase de NP, Gráfico disperso , Conjunto independiente Problema: Dada la gráfica G = (V, E) y dos enteros a y b . Un conjunto de varios vértices de G tales que hay como máximo b aristas entre ellos se conoce como el subgrafo disperso del grafo G. Explicación: … Continue reading «Demostrar que Sparse Graph es NP-Complete»
Problema SAT : SAT (Boolean Satisfiability Problem) es el problema de determinar si existe una interpretación que satisfaga una fórmula booleana dada. Pregunta si las variables de una fórmula booleana determinada se pueden reemplazar consistentemente por los valores VERDADERO o FALSO de tal manera que la fórmula se evalúe como VERDADERO . Si este es … Continue reading «Prueba de que SAT es NP Completo»
Prerrequisito: NP-Completeness , NP Class , Clique , Independent Set Problema: dado un gráfico no dirigido G = (V, E) y un número entero K , determine si existeuna camarilla de tamaño K , así como un conjunto independiente (IS) de tamaño K. Demostrar que es un NP Completo. Explicación: Un Clique es un subgrafo … Continue reading «Demostrar que un problema formado por Clique y Conjunto Independiente es NP Completo»
Problema de la ruta más larga optimizada : El problema de la ruta más larga optimizada establece que dado un gráfico G , de un conjunto de vértices V y aristas E , la tarea es demostrar que existe una ruta de longitud al menos K entre un conjunto de Nodes V s y V … Continue reading «La ruta más larga optimizada es NP Complete»