P/NP: Ciclo Hamiltoneano, Problema del Viajante, Coloreo de Grafos, Subset Sum, Clique Flashcards
Explique el problema del Ciclo Hamiltoneano
Sea G un grafo direccionado, definimos un ciclo C en G como hamiltoneano si:
- Visita cada vértice 1 vez y sólo 1 vez.
- Comienza y termina por el mismo vértice.
Entonces, dado un grafo, se desea saber si existe un ciclo hamiltoneano.
Ham-Cycle: ¿Es NP?
Ham-Cycle es NP.
Dado un certificado T que contenga una lista ordenada de vértices, puedo verificar en tiempo polinomial que:
- |T| = |V|
- t_0 = t_|V| (el primer nodo y el último son el mismo)
- Todos los vértices de V están en T
- Para todo par de vértices en T, existe un eje en el grafo.
Por lo tanto, es NP.
Ham-Cycle: ¿Es P?
No se conoce un algoritmoq ue resuelva a Ham-Cyle en tiempo polinómico. Si probamos que Ham-Cycle es NP-C, entonces Ham-Cycle sería P si y sólo si P = NP.
Explique la reducción de 3SAT a Ham-Cycle
Para I instancias de 3SAT:
- Con n variables x1, ..., xn
- k clàusulas c1, ..., cn
Construiremos un grafo G donde encontrar el ciclo hamiltoneano.
- Construimos
ncaminosp1, ..., pn, por donde cada uno representa a una variable. - Cada camino estará conformado por
2 * knodos, unidos entre sí por aristas de ida y vuelta. - Uniremos cada camino:
a. Desde su nodo inicial hasta el nodo inicial del camino siguiente.
b. Desde su nodo inicial hasta el nodo final del camino siguiente.
c. Desde su nodo final hasta el nodo inicial del camino siguiente.
d. Desde su nodo final hasta el nodo final del camino siguiente.
- Creamos nodos s,t y agregamos ejes:
a. s - v1,1 (primero de la primer fila)
b. s - v1,2k (último de la primer fila)
c. vn,1 - t (primero de la última fila)
d. vn,n - t (último de la última fila)
e. t - s
- Creamos 1 nodo por cada cláusula
Ti = (t1, t2, t3). - Para cada variable
xde la cláusulai:
a. Se unen 2 nodos del camino de la variable x con el nodo de la cláusula i en la posición i*2 y i*2+1. Si la variable no está negada, las direcciones van de nodo a cláusula y luego de cláusula a nodo. Sino, al revés.
Si existe un camino hamiltoneano que parte de s y llega a t (regresando luego a s), y pasando por todos los nodos, entonces hay forma de satisfacer la expresión booleana.
- El sentido por el que se recorre el camino determina si el valor de una variable es 0 ó 1: para la derecha, 1. Para la izquierda, 0.
- El eje seleccionado para acceder al nodo “ cláusula” nos dice qué varible la activa.
- Si una variable requiere estar negada y no estarla para activar varias cláusulas, el ciclo e simposible de construir.
Ham-Cycle: ¿Es NP-C?
Ham-Cycle es NP-C.
Como Ham-Cycle pertenece a NP y 3SAT es reducible a HAM-CYCLE, entonces:
Ham-Cycle pertenece a NP-C.
Explique el problema del viajante.
Dado:
- n ciudades
- Las distancias entre cada par de ciudades
Queremos determinar si existe un tour o ciclo de distancia total menor a k tal que se recorran las n ciudades.
Problema del viajante: ¿Es NP?
El problema del viajante es NP.
Sean n ciudades, las distancias entre cada par de ciudades, T un ceritificado y k la distancia como límite, se puede verificar que:
- T contenga a todas las ciudades sólo 1 vez, y que termine y comience en la misma.
- Que la suma total de la distancia recorrida sea menor a ´k´.
Explique la reducción de Ham-Cycle a Viajante.
Sea I una instancia de Ham-Cycle, tenemos un grafo G=(V,E) donde:
- Por cada vértice
v, creamos una ciudadvi. - Por cada arista
eij, definimos la distanciad(vi, vj) = 1. - Aquellas distancias que no están definidas (no tienen aristas) las crearemos con valor 2.
- Ponemos como valor
k = |V|(número de vértices).
Solucionamos viajante con k definido. Si existe un camino con longitud k, entonces existe un ciclo hamiltoneano.
Problema del viajante: ¿Es NP-C?
Como Ham-Cycle <=p Viajante, entonces el problema del viajante es NP-C.
Explique el problema de Coloreo de Grafos.
Sea un grafo G=(V,E) no dirigido, y una función F que le asigna un color a cada vértice; para todo eje e=(u,v) tal que f(u) != f(v)`.
Queremos colorear el grafo tal que nodos que tienen ejes entre sí no tengan el mismo color.
¿A qué se define como “número cromático X(G)`?
Definimos al número cromático X(G) como el menor número de colores necesario par colorear un grafo.
¿A qué se define como “polinomio cromático?
Definimos polinomio cromático a la ecuación que permite contar el número de maneras en las cuales puede ser coloreado un grafo usando no más de k colores.
¿A qué se llama “clase de color” y a qué se llama “conjunto k- partito?
Llamaremos clase de color al subconjutno de vértices coloreados con el mismo color.
Una k-coloración equivale a una partición de nodos en k conjuntos independientes. Si un grafo es k-coloreable, entonces es k- partito.
Explique el problema de decisión de Coloreo de Grafos.
Sean:
-
G = (V,E)un grafo no dirigido -
kun valor numérico.
Queremos determinar si es posible definir una función de coloreo que utilice k o menos colores.
Explique el caso especial del grafo completo
Si el grafo es simple y completo (todos los vértices están comunicados entre sí), se requiere un color por vértice para colorear el grafo.
Podemos saber si es completo si tiene:
|E| = |V| * ( |V| -1 ) / 2
Explique el caso especial del grafo bipartito
Un grafo bipartito requiere de sólo 2 colores para colorear el grafo. Podemos usar un algoritmo similar a BFS para colorear el grafo.
Coloreo de grafos: ¿Es NP?
Es NP.
Dado un grafo G, una cantidad de k colores, y un certificado T (que para cada vértice le asigna un color), puedo verificar en tiempo polinomial que:
- Todos los nodos de V están en T.
- La cantidad de colores usados en T es menor o igual a
k. - No existe en
Gdos vértices adyacentes que enTtengan el mismo color.
Por lo que el coloreo de grafos es NP.
Explique la reducción de 3SAT a Coloreo de Grafos
Dada una instancia I de 3SAT con k cláusulas y n variables, creamos:
- Diferentes gadgets que serán subgrafos para colorear.
- 1 gadget para las variables.
- 1 gadget por cláusula.
- Creamos un vértice para cada variable y su negación.
- Creamos los vértices especiales
T,F, yB(true, false y base). - Generamos los ejes:
a. Entre vi y ¬vi
b. Entre vi y ¬vi con B
c. T, F, B entre ellas.
Por lo tanto, la variable tendrá True si tiene el mismo color qu eT.
- Creamos un gadget para cada cláusula.
a. La cláusula ci = (a,b,c) con a,b,c pertenecientes a: {x1, ¬x1, ..., xn, ¬xn}.
b. Las variables de la cláusula corresponden a los nodos creados para las variables. Por ejemplo, si a = x1, el gadget ci,1 se conecta a v1.
El gadget va a tener la forma detallada en la siguiente imagen.
- Los nodos 1, 2, 3, 4 se conectan a T
- Los nodos 1, 2, 6, 5 se conectan entre sí de forma secuencial.
- Hay un eje entre 3 y 6 y entre 4 y 5
- 5 se conecta a F
- Los nodos c1, c3 y c4 de la cláusula se conectan a las variables que contiene: a, b, c.
- Definimos
k=3para los colores. - Si el grafo resultante se puede pintar con 3 colores, entonces la expresión
Ise puede satisfacer (los nodos correspondientes a las variables con igual color aTdeben estar entrue).
Entonces, con al menos 1 variable en True de la cláusula i, el subgrafo correspondiente al gadget de la cláusula i se puede colorear con 3 colores.
=> Si se requiere que 1 variable esté negada y sin negar, no se puede colorear el grafo.
Resuelva con la reducción de 3SAT a Coloreo de Grafos:
E = (x1,x2,x4) y (not x1, x3, x4)
x1 = 1
x2 = 1
x3 = 1
x4 = 0
Resuelva con coloreo de grafos:
Se tiene el grafo:
ejes:
(A,B) (A,D) (B,C) (C,D) (D,E) (D,F) (E,H) (E,G)
¿ Es k coloreable con k = 4?
Lo es.
Explique el problema de decisión Subset Sum
Sea un conjunto C = {w1, ..., wn} de número naturales, queremos determinar si existe un subconjunto de C que sume exactamente W.
Es un problema de decisión relacionado con el problema de la mochila.
Subset Sum: ¿Es P?
Subset sum no es P.
Usando programación dinámica, se puede resolver en tiempo pseudo polinomial O(Wn). Si representamos W en bits, el algoritmo crece exponencialmente a la cantidad de bits de W. No se conoce una solución polinomial, por lo que Subset Sum no es P.
Subset Sum: ¿Es NP?
Es NP.
Dados:
- Un
Cconjunto dennúmeros naturales. - W número a sumar
- T certificado con subconjunto de
C.
Podemos determinar polinomialmente que:
∑ (ti) = W, para todo ti en C
Por lo tanto, es NP.
Subset Sum: ¿Es NP-Hard?
Es NP-Hard, porque se puede reducir 3DM a Subset Sum. De esta forma, probamos que es NP-C. Si es NP-C, es NP-H.
Explique el objetivo de la reducción de 3DM a Subset Sum
Sea I una instancia de 3DM con X,Y,Z conjuntos de n elementos, T ⊆ X x Y x Z conjuntos de m triplas.
Queremos representar cada tripla como un vector de bits.
Explique la representación Vectorial para la reducción de 3DM a Subset Sum
Usamos vectores de 3 * n bits:
- Los primeros
nbits representan los elementos de X - Los siguientes
nrepresentan los elementos de Y - Los últimos
nrepresentan los elementos de Z.
A cada elemento de los conjuntos le asignamos un orden arbitrario de a n.posx(x), posy(y), posz(z) son las funciones que dado un elemento, retorna su posición en el set.
A cada t = {xi, yi, zi} tripla de T la representamos como un vector de 3n bits con todos los bits en cero, exceptuando los siguientes:
- posx(xi)
- posy(yj) + n
- posz(zk) + 2n
Los valores binarios se invierten para que al calcular luego w_i, la X quede en los bits menos significativos.
Explique la transformación en un número entero para la reducción de 3DM a Subset Sum
Cada vector vt se puede representar como un número t en el subconjunto subset sum.
El valor W lo formaremos como el vector con todos los bits en 1.
Para sumar W, tenemos que encontrar aquellos wt que nos den W. Pero no debo elegir 2 o más números con un mismo bit prendido, porque genera un overflow.
Para evitarlo, vamos a representar cada tripla como un número de la siguiente manera:
wt = d^(posx(xi)-1) + d^(posy(yj)+n-1) + d^(posz(zk)+2n-1)
Siendo d la base elegida. Vamos a usar d = m + 1, con m la cantidad de triplas.
Subset Sum: ¿Es NP-H?
Se puede reducir 3DM a Subset Sum.
3DM es NP-C (porque 3SAT es NP-C y se puede reducir a 3DM), entonces Subset Sum es NP-C; por lo tanto, es también NP-H.
Resuelva: Subset sum:
Sea la instancia de 3DM
X = x1, x2, x3
Y = y1, y2, y3
Z = z1, z2, z3
T = { (x1,y1,z1), (x2,y2,z3), (x3,y3,z1), (x1, y1, z2), (x3,y3,z2), (x1,y3,z2), (x3,y3,z3) }
W = 19173961
C = {(x1,y1,z1), (x2,y2,z3), (x3,y3,z2)}
Clique: Explique el problema
Sea un grafo G no dirigido, llamaremos clique a un subconjunto V’ incluído (o igual) en V, de vértices tal que para todo par de vértices, existe un eje que los conecta. Es decir, todos los vértices están conectados entre sí.
La cantidad de nodos en V’ determina el tamaño del clique.
Clique: Explique el problema de decisión
Dado un grafo G y un valor numérico k positivo, queremos ver si existe un clique de tamaño k en G.
Clique: ¿Es NP?
Es NP.
Dado un grafo G, un valor k de tamaño del clique y un certificado T que contiene un subconjutno de nodos de V, se puede verificar en tiempo polinomial que:
- La cantidad de nodos en T es igual a k
- Cada nodo en T está conectado a los otros nodos de T.
Clique: ¿Es P?
No es P.
Por fuerza fruta, la complejidad es exponencial.
Clique: ¿NP-Hard?
Sí, porque se puede reducir 3SAT a Clique. Como clique es NP-C, entonces es NP-H.
Explique la reducción 3SAT a Cliques
Dada una instancia I de 3SAT con k cláusulas y n variables:
- Creamos un nodo por cada variable en una cláusula.
- Por cada par de variables de diferentes cláusulas, creamos un eje entre ellas si no corresponden a la misma variable o negada.
- Buscamos un clique de tamaño
k.
Los nodos dentro del clique indican el valor de las variables como “True”. Aquellas que están fuera del clique pueden ser True o False.
Resuelva con la reducción 3SAT a Clique:
E = (x1,x2,x4) y (not x1, x3, x4) y (not x2, not x3, x4) y (not x1, x2, not x4)
Haga un resumen de todas las reducciones vistas.
- Set cover >= cobertura de vértices >= conj. indep. >= 3SAT
- Subset sum >= 3DM >= 3SAT
- Coloreo >= 3SAT
- Clique >= 3SAT
Recordamos el Teorema de Cook-Levin:
Para todo X perteneciente a NP: X <= 3SAT
Por lo que 3SAT es de los problemas más complejos de resolver en NP.
=> 3SAT pertenece a NP-C.
