P/NP: Pruebas, Conjunto Independiente, Cobertura de Vértices, Set Cover, 3 Dimensional Matching Flashcards
Explicar cómo se puede probar que un problema X es NP-Hard
Sea X un problema de decisión, queremos probar que un problema Z que es NP-Hard puede ser reducido polinomialmente a X:
- Z pertenece a NP-Hard
- Z <=p X
=> X pertenece a NP-Hard.
¿Qué significa que Z sea NP-H?
Que Z sea NP-H significa que todos los problemas Y de NP pueden ser reducidos a Z. Y si Z puede ser reducido a X, entonces todos los problemas Y pueden ser reducidos a X. Por lo tanto, X pertenece a NP-H.
Explicar cómo se puede probar que un problema X es NP-C
Sea X el problema de decisión, queremos probar que X pertenece a NP - C.
- Probamos que X pertenece a NP
a. Conseguimos un algoritmo de verificación en tiempo polinómico no determinístico.
b. Dado un certificado válido, verificamos que el resultado devuelva true.
- Probamos que X pertence a NP-H
a. Dado un problema Y de NP-C (o NP-H), reducimos polinomialmente Y a X tal que Y <=p X.
b. Entonces, si Y pertence a NP-C/H e Y <=p X, entonces significa que X es NP-H.
De esta forma:
- Transformamos de forma polinomial la entrada de
Yen una entrada equivalente deX - Resolvemos
- Transformamos de forma polinomial la salida de
Xen una salida equivalente para el problemaY.
¿Se puede probar que P = NP?
Los pasos para probar que P = NP son:
- Tomar un problema X NP-C
- Construir un algoritmo que resuelva X en tiempo polinomial.
Como todo problema NP-C se puede reducir entre si con igual complejidad y todo problema NP se puede reducir a otro NP-C
Entonces existe un algoritmo polinomial para todo problema NP tal que P = NP.
La cuestión de si P es igual a NP es uno de los problemas más importantes en el campo de la teoría de la complejidad computacional.
Hasta el momento, no se ha resuelto si P = NP.
Explique el problema de Conjunto Independiente
Sean:
- Un grafo
G = (V, E) - Un valor
k
Determinar si existe un conjunto independiente de nodos de como mucho tamaño k.
Un conjunto de nodos es independiente si no existe ejes que los una entre sí. El tamaño del conjunto corresponde a la cantidad de nodos dentro del mismo.
¿Conjunto independiente es NP?
Conjunto independiente es NP.
Dado un grafo G, un tamaño k y un subconjunto T de nodos del grafo, yo puedo verificar en tiempo polinomial dos cosas:
- Si |T| = k
- Si no existen ejes que conecten a dos nodos entre sí dentro del conjunto
T.
¿Conjunto Independiente es P?
Conjunto independiente no es P.
No se conoce algoritmo que resuelva Conjunto Independiente en tiempo polinómico.
Si logramos probar que Conjunto Independiente es NP-C, entonces sería P si y sólo si P = NP.
Explique la reducción de 3SAT a Conjunto Independiente
- Para la cláusula
Ti = (ti1 v ti2 v ti3)se crean 3 vértices conectados entre sí. - Por cada
tij = xaytkl = ¬ xa(por cada nodo creado y otro nodo con esa misma variable negada, crear un eje entre ellos. - El grafo resultante se llama G y es una instancia del problema.
Ahora, queremos encontrar un set independiente de k elementos, siendo k el número de cláusulas en la expresión.
3SAT a Conjunto Independiente:
Realice la reducción para la siguiente expresión de 2 cláusulas:
E = (x1, x2, x3) y ( ¬x1, ¬x2, ¬x4)
k = 2
El grafo obtenido es:
[ (x1, ~x1), (x1, x2), (x1, x2), (x2,x,3), (x2, ~x2), (~x1,~x2), (~x1, ~x4), (~x2, ~x4)]
Conjunto independiente elegido: (~x1, x2)
Esto significa que con ~x1 = 1 y x2 = 1, el valor de E es True. Cualquier certificado (0,1,x3,x4) verifica que E es true.
Pudimos verificar que el Conjunto Independiente es NP-C, porque:3SAT <=p Conj. Independiente
Cobertura de Vértices: Explique el problema.
Sea G un grafo, diremos que S⊆ V es una cobertura de vértices si para todo eje del grafo, al menos uno (puedenser los dos) de sus vértices pertenece a S.
Cobertura de Vértices: Explique el problema de decisión
Sea un grafo G, determinar si existe una cobertura de vértices de tamaño al menos k.
Cobertura de Vértices: ¿Es NP?
Sí.
Sea un grafo G y un certificado t (conjunto de nodos que forman el cubrimiento), podemos verificar:
|t|= k- Para toda arista, uno o dos de los vértices pertenece a ´t´. Esto es O(V * E).
Explique la reducción de conjunto independiente a vertex cover
Sea un grafo G y un conjunto independiente S de tamaño |S|, llamaremos C = V - S al complemento de S.
Decimos que para todo eje e=(u,v), u pertenece a S y v pertenece a C (porque S es independiente). Entonces, V-S es una cobertira de vértices de tamaño |V-S|.
¿Cómo se transforma un problema de vertex cover en uno de conjunto independiente?
- Sea G un grafo de V vértices.
- Sea k el tamaño de la cobertura de vértices.
| V | - k = k*- Planteo un problema de set independiente con
k*. - Si encuentro un conjunto independiente, entonces el conjunto de cobertura es C = V - S.
Vertex cover: ¿Es NP-C?
Podemos ver que:
- 3SAT <=p Conjunto Independiente
- Conjunto independiente <=p cobertura de vértices
- Cobertura de vértices <=p Conjunto independiente
Por lo tanto, tienen la misma complejidad => Cobertura de vértices es NP-C.
Explique el problema Set Cover.
Sea un conjunto U de n elementos y una colección S1,..., Sn de subconjuntos de U, queremos ver si existe una colección de como mucho k de los subconjuntos cuya unión es igual a U.
Set Cover: ¿Es NP?
Set Cover es NP.
Dado un conjunto U de elementos, k un tamaño bsucado de set de subconjuntos, y sean S1,..., Snlos subconjuntos de U.
Dado un certificado T, con subconjunto de conjuntos, debemos verificar que |T| = k.
Además, verificar que para todo elemento de U existe en alguno de los subconjuntos de T se puede verificar en tiempo polinomial.
Explique la reducción de Vertex Cover a Set Cover
Partimos de G = (V,E) y k.
Queremos que todos los ejes queden cubiertos.
Entonces:
- Contruimos un set de elementos
U = E(ejes del grafo). - Por cada vértice
v, creamos un subconjuntoSvcon todos los ejes incidentes en èl (unimos los ejes en subconjuntos por vértice). - La cantidad de subconjuntos a buscar para cubrir U sigue siendo
k.
Si encontramos el subconjunto, los subconjuntos nos dirán qué vértices debemos seleccionar.
Set Cover: ¿Es NP-C?
3Podemos reducir Vertex cover a Set Cover en tiempo polinomial:
Vertex Cover <=p Set Cover.
Como Vertex Cover es NP-C, entonces Set Cover es NP-C.
Recordemos:
3SAT <=p Conjunto Independiente <=p Vertex Cover <=p Set Cover
Como 3SAT es NP-C (NP y NP-H), Set Cover es NP-C.
Sea el grafo con los siguientes ejes:
1-2, 1-4, 2-3, 3-4, 4-5, 4-6, 5-7, 5-8
Reduciendo a Set Cover, indique si hay una cobertura de vértices de tamaño k = 3
La hay.
2, 4, 5 es una posible.
Explique el problema 3 Dimensional Matching
Dados:
- 3 sets disjuntos X, Y, Z de tamaño
ncada uno - Un set C ⊆ X, Y, Z de triplas ordenadas
Queremos determinar si existe un subset de n triplas en C tal que cada elemento de ` X u Y u Z` (la unión) sea contenido exactamente en una de esas triplas.
Ejemplo:
S1 = {A,B}
S2 = {C, D}
S3 = {E,F}
C = { (A,C,E), (B,D,F)}
3 Dimensional Matching: ¿Es NP?
3DM es NP.
Dado un certificado de triplas con subconjuntos de C, podemos certificar en tiempo polinomial que:
- |T| = n
- Todo elemento de X,Y,Z se encuentra 1 y sólo 1 vez en algún Ti.
Por lo tanto, 3DM es NP.
3 Dimensional Matching: ¿Es NP-C?
3DM es NP-C.
- 3DM está en NP
- Se puede reducir 3SAT a 3DM (3SAT 1<=p 3DM, explicación obviada en estas flashcards porque es muy largo)
- 3SAT pertenece a NP-C
=> 3DM pertenece a NP-C
Resuelva:
Reducción de conjunto independiente a cobertura de vértices
Se tiene el grafo:
ejes:
(A,B) (A,D) (B,C) (C,D) (D,E) (D,F) (E,H) (E,G)
¿Existe una cobertura de k = 7?
Existe.
El conjunto independiente tiene k = 1, puedo elegir cualquier nodo. El resto pertenecen a la cobertura de vertices.
