P/NP: Pruebas, Conjunto Independiente, Cobertura de Vértices, Set Cover, 3 Dimensional Matching

Question 1

Explicar cómo se puede probar que un problema X es NP-Hard

Answer 1

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.

Question 2

¿Qué significa que Z sea NP-H?

Answer 2

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.

Question 3

Explicar cómo se puede probar que un problema X es NP-C

Answer 3

Sea X el problema de decisión, queremos probar que X pertenece a NP - C.

1. 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.

2. 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 Y en una entrada equivalente de X
• Resolvemos
• Transformamos de forma polinomial la salida de X en una salida equivalente para el problema Y.

Question 4

¿Se puede probar que P = NP?

Answer 4

Los pasos para probar que P = NP son:

1. Tomar un problema X NP-C
2. 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.

Question 5

Explique el problema de Conjunto Independiente

Answer 5

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.

Question 6

¿Conjunto independiente es NP?

Answer 6

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.

Question 7

¿Conjunto Independiente es P?

Answer 7

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.

Question 8

Explique la reducción de 3SAT a Conjunto Independiente

Answer 8

• Para la cláusula Ti = (ti1 v ti2 v ti3) se crean 3 vértices conectados entre sí.
• Por cada tij = xa y tkl = ¬ 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.

Question 9

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)

Answer 9

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

Question 10

Cobertura de Vértices: Explique el problema.

Answer 10

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.

Question 11

Cobertura de Vértices: Explique el problema de decisión

Answer 11

Sea un grafo G, determinar si existe una cobertura de vértices de tamaño al menos k.

Question 12

Cobertura de Vértices: ¿Es NP?

Answer 12

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).

Question 13

Explique la reducción de conjunto independiente a vertex cover

Answer 13

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|.

Question 14

¿Cómo se transforma un problema de vertex cover en uno de conjunto independiente?

Answer 14

1. Sea G un grafo de V vértices.
2. Sea k el tamaño de la cobertura de vértices.
3. | V | - k = k*
4. Planteo un problema de set independiente con k*.
5. Si encuentro un conjunto independiente, entonces el conjunto de cobertura es C = V - S.

Question 15

Vertex cover: ¿Es NP-C?

Answer 15

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.

Question 16

Explique el problema Set Cover.

Answer 16

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.

Question 17

Set Cover: ¿Es NP?

Answer 17

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.

Question 18

Explique la reducción de Vertex Cover a Set Cover

Answer 18

Partimos de G = (V,E) y k.
Queremos que todos los ejes queden cubiertos.

Entonces:

1. Contruimos un set de elementos U = E (ejes del grafo).
2. Por cada vértice v, creamos un subconjunto Sv con todos los ejes incidentes en èl (unimos los ejes en subconjuntos por vértice).
3. 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.

Question 19

Set Cover: ¿Es NP-C?

Answer 19

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.

Question 20

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

Answer 20

La hay.
2, 4, 5 es una posible.

Question 21

Explique el problema 3 Dimensional Matching

Answer 21

Dados:

• 3 sets disjuntos X, Y, Z de tamaño n cada 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)}

Question 22

3 Dimensional Matching: ¿Es NP?

Answer 22

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.

Question 23

3 Dimensional Matching: ¿Es NP-C?

Answer 23

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

Question 24

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?

Answer 24

Existe.
El conjunto independiente tiene k = 1, puedo elegir cualquier nodo. El resto pertenecen a la cobertura de vertices.