Categoría: Algorithms-NP Complete

Tipos de clases de complejidad | P, NP, CoNP, NP duro y NP completo

Posted on by Rudeus Greyrat

En informática existen algunos problemas cuyas soluciones aún no se encuentran, los problemas se dividen en clases conocidas como Clases de Complejidad . En la teoría de la complejidad, una clase de complejidad es un conjunto de problemas relacionados con la complejidad. Estas clases ayudan a los científicos a agrupar problemas en función de cuánto … Continue reading «Tipos de clases de complejidad | P, NP, CoNP, NP duro y NP completo»

Prueba de que el problema de decisión de camarilla es NP-Complete | conjunto 2

Posted on by Rudeus Greyrat

Requisito previo: NP-Completo , problema de camarilla . Una camarilla en un gráfico es un conjunto de vértices donde cada vértice comparte un borde con todos los demás vértices. Así, una camarilla en un grafo es un subgrafo que es un grafo completo. Problema: Dada una gráfica G(V, E) y un entero K, el problema … Continue reading «Prueba de que el problema de decisión de camarilla es NP-Complete | conjunto 2»

Diferencia entre problema NP difícil y NP completo

Posted on by Rudeus Greyrat

Requisito previo: NP-Completitud  Problema NP:  El conjunto de problemas NP cuyas soluciones son difíciles de encontrar pero fáciles de verificar y se resuelven mediante una máquina no determinista en tiempo polinomial.  Problema NP-Difícil :  Un problema X es NP-Difícil si hay un problema NP-Completo Y, tal que Y es reducible a X en tiempo polinomial. … Continue reading «Diferencia entre problema NP difícil y NP completo»

Prueba de que la cobertura de vértices es NP completa

Posted on by Rudeus Greyrat

Requisito previo: problema de cobertura de vértices , problema de NP-completitud : dado un gráfico G (V, E) y un número entero positivo k, el problema es encontrar si hay un subconjunto V ‘de vértices de tamaño como máximo k, tal que cada borde en el gráfico está conectado a algún vértice en V’. Explicación: … Continue reading «Prueba de que la cobertura de vértices es NP completa»

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

Posted on by Rudeus Greyrat

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»

Prueba de que el ciclo hamiltoniano es NP-Completo

Posted on by Rudeus Greyrat

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»

Prueba de que el problema de isomorfismo de subgrafo es NP-Completo

Posted on by Rudeus Greyrat

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»

Teorema de Cook-Levin o teorema de Cook

Posted on by Rudeus Greyrat

En la teoría de la complejidad computacional, el teorema de Cook-Levin, también conocido como teorema de Cook, establece que el problema de satisfacibilidad booleano es NP-completo. Es decir, está en NP, y cualquier problema en NP puede reducirse en tiempo polinomial mediante una máquina de Turing determinista al problema booleano de satisfacibilidad. Stephen Arthur Cook … Continue reading «Teorema de Cook-Levin o teorema de Cook»

Algoritmos | NP Completo | Pregunta 1

Posted on by Rudeus Greyrat

Suponiendo que P != NP, ¿cuál de las siguientes es verdadera? (A) NP-completo = NP (B) NP-completo P = (C) NP-duro = NP (D) P = NP-completo (A) A (B) B (C) C (D) D Respuesta: (B) Explicación: La respuesta es B (ningún problema NP-Completo se puede resolver en tiempo polinomial). Porque, si un problema … Continue reading «Algoritmos | NP Completo | Pregunta 1»

Prueba de que el conjunto independiente en la teoría de grafos es NP completo

Posted on by Rudeus Greyrat

Requisito previo: NP-Completo , Conjunto independiente . Un Conjunto Independiente S del gráfico G = (V, E) es un conjunto de vértices tales que no hay dos vértices en S adyacentes entre sí. Consta de vértices no adyacentes. Problema: Dada una gráfica G(V, E) y un entero k, el problema es determinar si la gráfica … Continue reading «Prueba de que el conjunto independiente en la teoría de grafos es NP completo»