NP-completitud

La semana pasada definimos P y NP, escribimos reducciones polinomiales A ≤ₚ B y vimos que conjunto independiente, cobertura de vértices y clique se transforman uno en otro. Pero quedó un hueco. Una reducción solo traslada la dificultad: si A es difícil, B también. Todas esas transformaciones dicen “estos problemas son igual de difíciles entre sí”, sin decir que alguno lo sea. Hace falta un primer problema, del que se sepa algo por otra vía.

Ese primer problema es SAT, y el resultado que lo ancla es el teorema de Cook-Levin: todo problema de NP se reduce a SAT. Con eso, la semana se vuelve una cadena de construcciones. Partimos cláusulas largas para llegar a 3-SAT. De 3-SAT pasamos a conjunto independiente, con un triángulo por cláusula. Después a 3-coloreo, con unos grafos pequeños que se portan como compuertas lógicas. Después, de cobertura de vértices a suma de subconjuntos, donde una tabla de dígitos escribe un grafo dentro de un número. Y de ahí a la mochila, que dejamos pendiente desde la semana 7.

Cada reducción tiene la misma estructura que las de flujo de la semana 12: transformar y demostrar dos direcciones. Lo que cambia es para qué sirve. En flujo reducíamos para resolver. Aquí reducimos para mostrar que un problema es al menos tan difícil como otro.

La segunda sesión termina en la frontera: 2-SAT se resuelve en tiempo lineal con las componentes de la semana 6, y 3-SAT no se sabe resolver en tiempo polinomial. Una letra más en la cláusula cambia todo. Lo mismo pasa con otros tres pares de problemas que se ven casi iguales.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, de NP-difícil y NP-completo el apartado NP-difícil no es lo mismo que NP-completo, La receta, Un mapa de problemas y NP-completo no quiere decir irresoluble.

En clase: Sesión A, de NP-difícil y NP-completo a De 3-SAT a conjunto independiente. Sesión B, de De 3-SAT a 3-coloreo a Cerca de la frontera.

Después de clase: el Resumen y los Ejercicios, para repasar, y los resúmenes de las semanas 11 a 13 para la Práctica 4. Opcional: El código de la semana y su problema. Para ampliar, las lecturas de apoyo del recuadro siguiente.

Lectura. Sesión A: Erickson, secs. 12.3 (NP-hard, NP-easy, and NP-complete) y 12.7 (Maximum Independent Set (from 3Sat)). Sesión B: Erickson, secs. 12.10 (Graph Coloring), 12.12 (Subset Sum) y 12.14 (Choosing the Right Problem). CLRS, capítulo NP-Completeness, 4.ª edición. Estos apuntes se pueden estudiar sin ellos.

Código. Los programas de este capítulo están en code/week-14. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. Esta semana la sesión de laboratorio es para la Práctica 4, y el problema lab/two_sat queda como ejercicio opcional.

NP-difícil y NP-completo

Recordemos lo de la semana 13. Un problema de decisión tiene respuesta sí o no. El tamaño de una entrada se mide en bits. P son los problemas que se resuelven en tiempo polinomial. NP son aquellos en que cada respuesta “sí” tiene un certificado de tamaño polinomial que se verifica en tiempo polinomial. A ≤ₚ B significa que hay una transformación en tiempo polinomial que lleva cada instancia de A a una instancia de B con la misma respuesta. Y estas reducciones se componen: si A ≤ₚ B y B ≤ₚ C, entonces A ≤ₚ C.

Dos definiciones nuevas.

Definición. Un problema X es NP-difícil (NP-hard) si todo problema A de NP cumple A ≤ₚ X.

Definición. Un problema X es NP-completo (NP-complete) si está en NP y es NP-difícil.

Un problema NP-completo es, entonces, de los más difíciles de NP: está adentro y todos los demás se le pueden traducir. Eso tiene una consecuencia que explica por qué este concepto importa tanto.

Teorema. Sea X un problema NP-completo. X está en P si y solo si P = NP.

Técnica. Dos direcciones, directas, con la definición.

Si X está en P. Tomemos cualquier A de NP. Como X es NP-difícil, A ≤ₚ X. Para resolver A en una entrada de s bits, se transforma en tiempo polinomial en s. La salida no puede tener más bits que los pasos usados para escribirla, así que su tamaño también es polinomial en s. Se corre sobre ella el algoritmo de X, polinomial en ese tamaño. Un polinomio de un polinomio es un polinomio. Luego A está en P. Como A era cualquiera, NP ⊆ P. La inclusión P ⊆ NP ya se sabía, y entonces P = NP.

Si P = NP. X está en NP, y por lo tanto en P. ∎

Esto es lo que la frase “si uno solo de ellos está en P, todos lo están” quiere decir. Vale para los NP-completos: si uno cae, caen todos, y si P ≠ NP, ninguno está en P. Hoy nadie sabe si P = NP. La mayoría de los investigadores cree que no, pero es una creencia, y no un resultado.

Idea clave. Demostrar que un problema es NP-completo no demuestra que sea imposible de resolver rápido. Demuestra algo más modesto y muy útil: un algoritmo polinomial para él resolvería de golpe miles de problemas en los que mucha gente ya fracasó.

NP-difícil no es lo mismo que NP-completo

La definición de NP-difícil no exige estar en NP. Hay problemas NP-difíciles fuera de NP, y el ejemplo clásico es el problema de la parada (halting problem): dado un programa y una entrada, ¿el programa termina?

Es NP-difícil. Como vamos a ver enseguida, todo problema de NP se reduce a SAT, y las reducciones se componen. Basta, entonces, reducir SAT al problema de la parada. Dada una fórmula φ, escribimos un programa que prueba todas las asignaciones de φ en orden. Si alguna cumple φ, termina. Si no queda ninguna, entra en un ciclo infinito. Ese programa se escribe en tiempo polinomial: no se corre, solo se imprime su texto, y es un texto fijo más la fórmula. Termina si y solo si φ se puede cumplir.

No está en NP. Todo problema de NP se decide con un algoritmo, aunque sea lento: probar todos los certificados posibles. Y el problema de la parada es indecidible: ningún algoritmo lo resuelve. Esto se demuestra en Teoría de la Computación, y aquí lo usamos enunciado.

Por eso la frase de arriba no vale para los NP-difíciles en general. El problema de la parada es NP-difícil, y no va a estar en P aunque resulte que P = NP.

La otra fuente de confusión son las versiones de optimización. “¿Cuál es el conjunto independiente más grande?” no es un problema de decisión, de modo que no está en NP por una razón de tipo, y A ≤ₚ X como la definimos no se aplica. Aun así, es común oírlo llamar NP-difícil. En ese uso más amplio la frase significa: un algoritmo polinomial para él daría uno para un problema NP-completo, y entonces P = NP. Es un buen uso, siempre que se sepa cuál de las dos definiciones se está aplicando.

Cook-Levin

Una reducción necesita un punto de partida, y el primer problema difícil no se puede obtener por reducción desde otro. Lo da este teorema.

Teorema (Cook-Levin). SAT es NP-completo, incluso restringido a fórmulas en CNF.

Lo enunciamos sin demostrar: la demostración va en Teoría de la Computación. La intuición es esta. Si A está en NP, tiene un verificador que corre en tiempo polinomial. Su ejecución completa se puede dibujar como una tabla de bits, con una fila por paso. Que cada fila salga correctamente de la anterior es una regla local, y se escribe con cláusulas. La fórmula resultante se puede cumplir si y solo si existe un certificado que el verificador acepta.

En este capítulo SAT significa siempre SAT en CNF: la entrada es un Y de cláusulas, cada cláusula es un O de literales, y cada literal es una variable o su negación, como en DIMACS. Es la forma del enunciado de arriba, y la que usamos para partir cláusulas.

SAT está en NP, porque el certificado es la asignación, y se revisa en tiempo lineal. La función satisfies de cnf.h es ese verificador. Lo que Cook-Levin agrega es la otra mitad.

La receta

El teorema que convierte Cook-Levin en una herramienta es corto.

Teorema. Si X está en NP, A es NP-completo y A ≤ₚ X, entonces X es NP-completo.

Técnica. Transitividad. X ya está en NP. Sea Y cualquier problema de NP. Como A es NP-difícil, Y ≤ₚ A. Y como A ≤ₚ X, se compone y queda Y ≤ₚ X. ∎

De ahí sale la receta. Para demostrar que un problema X es NP-completo:

1. Está en NP. Digan cuál es el certificado, y por qué es de tamaño polinomial y se verifica en tiempo polinomial.
2. Elegir un problema A que ya se sabe que es NP-completo. Vamos a ver más adelante cuál conviene según el problema.
3. Transformar: de cada instancia de A se construye una de X. El sentido es de A hacia X, del conocido al nuevo.
4. Demostrar las dos direcciones: si la instancia de A tiene respuesta sí, la de X también. Si la de X tiene respuesta sí, la de A también. La segunda es lo mismo que decir que si A responde no, X responde no.
5. Comprobar el tiempo polinomial de la transformación, medido en bits de la entrada.

Compárenla con la de flujo de la semana 12. Las dos direcciones son iguales. Lo que cambia es que aquí no se necesita ningún algoritmo para X: la transformación solo tiene que existir y ser correcta.

Error común. Olvidar demostrar que el problema está en NP. Sin el paso 1 solo se demostró que es NP-difícil, que no es lo mismo. La reducción de arriba, de SAT al problema de la parada, cumple los pasos 2 a 5 sin problemas, y ese problema no es NP-completo. El paso 1 suele ser una línea, pero no siempre es obvio: para “¿esta fórmula no tiene solución?” nadie conoce un certificado corto. Mostrar que todas las asignaciones fallan parece requerir mirarlas todas.

Error común. Reducir al revés, como en la semana 13. Si reducen X a SAT, solo muestran que X no es más difícil que SAT, y eso también lo cumplen los problemas fáciles. Cualquier problema de P se reduce a SAT.

De SAT a 3-SAT

Una fórmula general es incómoda para diseñar gadgets, porque sus cláusulas tienen cualquier largo. Conviene un problema con todas las cláusulas iguales.

Definición. En 3-SAT, la entrada es una fórmula en CNF donde cada cláusula tiene exactamente tres literales, de tres variables distintas. La pregunta es si alguna asignación la cumple.

Existen otras versiones. Algunos textos dicen “a lo sumo tres literales”. Esa versión también es NP-completa: está en NP, y contiene a la nuestra como caso particular, porque una fórmula con exactamente tres es también una fórmula con a lo sumo tres. Aquí usamos “exactamente tres” porque hace más limpios los gadgets de las secciones que siguen.

Teorema. 3-SAT es NP-completo.

Está en NP: es un caso particular de SAT, con el mismo certificado.

La transformación. Reducimos SAT a 3-SAT, cláusula por cláusula. Primero limpiamos: se quitan los literales repetidos, y se borra toda cláusula que contenga x y ¬x, porque siempre se cumple. Después, cada cláusula limpia C de k literales se reemplaza según su largo. Las variables yᵢ son nuevas: cada una aparece solo en lo que sale de esa cláusula.

La cadena de una cláusula larga (ℓ₁ ∨ ℓ₂ ∨ … ∨ ℓₖ) usa k − 3 variables nuevas, y da k − 2 cláusulas:

(ℓ₁ ∨ ℓ₂ ∨ y₁)
(¬y₁ ∨ ℓ₃ ∨ y₂)
(¬y₂ ∨ ℓ₄ ∨ y₃)
...
(¬yₖ₋₃ ∨ ℓₖ₋₁ ∨ ℓₖ)

La idea de yⱼ es: “el literal verdadero está más adelante”. Cada eslabón dice: si me dijeron que está más adelante, entonces es este literal, o sigue estando más adelante. El último eslabón ya no tiene dónde pasarlo.

La fórmula de salida no es equivalente a la de entrada, porque tiene otras variables. Es equisatisfactible: una se puede cumplir si y solo si la otra se puede cumplir. Para una reducción, eso es exactamente lo que hace falta.

$ build/three_sat_demo
Una cláusula larga se parte en una cadena:
entrada: (x1 ∨ x2 ∨ x3 ∨ x4 ∨ x5 ∨ x6)
salida, con 9 variables y 4 cláusulas:
  (x1 ∨ x2 ∨ x7)
  (¬x7 ∨ x3 ∨ x8)
  (¬x8 ∨ x4 ∨ x9)
  (¬x9 ∨ x5 ∨ x6)
  fuerza bruta: entrada satisfacible, salida satisfacible

Una cláusula corta se rellena con variables nuevas:
entrada: (x1)
salida, con 3 variables y 4 cláusulas:
  (x1 ∨ x2 ∨ x3)
  (x1 ∨ x2 ∨ ¬x3)
  (x1 ∨ ¬x2 ∨ x3)
  (x1 ∨ ¬x2 ∨ ¬x3)
  fuerza bruta: entrada satisfacible, salida satisfacible

entrada: (x1 ∨ ¬x2)
salida, con 3 variables y 2 cláusulas:
  (x1 ∨ ¬x2 ∨ x3)
  (x1 ∨ ¬x2 ∨ ¬x3)
  fuerza bruta: entrada satisfacible, salida satisfacible

Repetidos y cláusulas que siempre se cumplen:
entrada: (x1 ∨ x1 ∨ ¬x2 ∨ x1)
salida, con 3 variables y 2 cláusulas:
  (x1 ∨ ¬x2 ∨ x3)
  (x1 ∨ ¬x2 ∨ ¬x3)
  fuerza bruta: entrada satisfacible, salida satisfacible

entrada: (x1 ∨ ¬x1 ∨ x2)
salida, con 2 variables y 0 cláusulas:
  (ninguna)
  fuerza bruta: entrada satisfacible, salida satisfacible
...

La demostración

Qué se afirma. La fórmula de entrada φ se puede cumplir si y solo si la de salida φ′ se puede cumplir.

Técnica. Se razona por cláusula, porque las variables nuevas de cada una son solo suyas. Por eso alcanza con mostrar: una asignación de las variables originales cumple C si y solo si se puede extender a las variables nuevas de C de modo que se cumpla todo lo que reemplazó a C. Limpiar no cambia nada: quitar un literal repetido no cambia cuándo se cumple la cláusula, y una cláusula con x y ¬x se cumple siempre.

Largo 0. C nunca se cumple, y las 8 cláusulas sobre tres variables tampoco, ya que cada asignación de esas tres falla en exactamente una de ellas.

Largo 1. Si ℓ es verdadero, las cuatro cláusulas se cumplen, con cualquier valor de y₁ e y₂. Si ℓ es falso, quedan las cuatro combinaciones de y₁ e y₂, y cada valor de ellas falla en una.

Largo 2. Si ℓ₁ o ℓ₂ es verdadero, las dos cláusulas se cumplen. Si los dos son falsos, quedan (y₁) y (¬y₁), que no se cumplen a la vez.

Largo 3. No cambia.

Largo k ≥ 4, de C a la cadena. Sea ℓᵢ un literal verdadero de C. Damos a yⱼ el valor verdadero si i ≥ j + 2, y falso si no. Es decir, yⱼ dice que el literal elegido está después de ℓⱼ₊₁. Revisemos cada eslabón.

• Primero, (ℓ₁ ∨ ℓ₂ ∨ y₁). Si i ≤ 2, se cumple por ℓᵢ. Si i ≥ 3, y₁ es verdadera.
• Intermedio, (¬yⱼ₋₁ ∨ ℓⱼ₊₁ ∨ yⱼ). Si i ≤ j, entonces yⱼ₋₁ es falsa, y se cumple por ¬yⱼ₋₁. Si i = j + 1, se cumple por ℓⱼ₊₁. Si i ≥ j + 2, yⱼ es verdadera.
• Último, (¬yₖ₋₃ ∨ ℓₖ₋₁ ∨ ℓₖ). Si i ≤ k − 2, entonces yₖ₋₃ es falsa. Si i ≥ k − 1, se cumple por ℓᵢ.

Largo k ≥ 4, de la cadena a C. Supongamos que se cumple toda la cadena, y que todos los ℓᵢ son falsos. El primer eslabón obliga a que y₁ sea verdadera. Si yⱼ₋₁ es verdadera, en el eslabón siguiente ¬yⱼ₋₁ y ℓⱼ₊₁ son falsos, y eso obliga a que yⱼ sea verdadera. Por inducción, yₖ₋₃ es verdadera. Entonces el último eslabón tiene sus tres literales falsos. Contradicción: algún ℓᵢ es verdadero. ∎

Sigamos la dirección de ida en el ejemplo de la cadena, con x4 como literal verdadero, es decir i = 4:

Extender x4 = V en la cadena: x1=F x2=F x3=F x4=V x5=F x6=F x7=V x8=V x9=F
  (x7, x8, x9 son y1, y2, y3)
  ¿cumple la salida? sí

Forma y tiempo. Cada cláusula de salida usa tres variables distintas, porque las nuevas no aparecen en otra parte y la limpieza dejó variables distintas en cada cláusula. Una cláusula de k literales da a lo sumo máx(k, 8) cláusulas y a lo sumo máx(k, 3) variables nuevas. El total es lineal en el número de literales y de cláusulas de φ, y el número de una variable ocupa O(log n) bits, con n la cantidad de variables. La transformación es polinomial.

inline Formula to_three_sat(const Formula& f) {
    Formula out{f.variables, {}};
    Clause c;
    for (const Clause& input : f.clauses) {
        if (!clean_clause(input, c)) continue;
        const std::size_t k = c.size();
        // ... k = 0, 1, 2 y 3, como en la tabla ...
        // Una cadena: yⱼ dice "el literal verdadero está más adelante".
        int y = ++out.variables;
        out.clauses.push_back({c[0], c[1], y});
        for (std::size_t i = 2; i + 2 < k; i++) {
            int next = ++out.variables;
            out.clauses.push_back({-y, c[i], next});
            y = next;
        }
        out.clauses.push_back({-y, c[k - 2], c[k - 1]});
    }
    return out;
}

test_examples.cpp corre esto en 1500 fórmulas al azar con cláusulas de hasta 7 literales, repetidos y x ∨ ¬x. Comprueba que toda cláusula de salida tiene tres variables distintas, que la fuerza bruta da la misma respuesta a los dos lados cuando la salida tiene hasta 14 variables, que restringir una solución de la salida cumple la entrada, y que extend_assignment, que es la dirección de ida escrita como código, da una solución de la salida.

Idea clave. Las variables nuevas son mensajes internos de una cláusula: “todavía no apareció el verdadero, sigan buscando”. Por eso no se pueden compartir entre cláusulas. Si se reutilizaran, un mensaje de una cláusula obligaría a otra.

¿Por qué no seguir partiendo hasta tener cláusulas de dos literales? Un eslabón necesita el mensaje que recibe, el literal que aporta y el mensaje que manda: tres cosas. Con dos no alcanza, y no es una falta de ingenio con este truco en particular: 2-SAT se resuelve en tiempo lineal, como vamos a ver al final del capítulo. Una reducción así demostraría que P = NP.

De 3-SAT a conjunto independiente

Un conjunto independiente (independent set) es un conjunto de nodos sin aristas entre ellos. El problema de decisión pregunta, dado un grafo G y un entero k, si G tiene uno de tamaño k. Vieron en la semana 13 que un certificado es el conjunto, y que se revisa en tiempo polinomial. Así que está en NP.

La fórmula tiene dos clases de reglas: en cada cláusula, al menos un literal debe ser verdadero; y una variable y su negación no pueden ser verdaderas a la vez. El grafo tiene una clase de arista por cada una.

La transformación. Dada una fórmula φ con m cláusulas de tres literales:

• Cada cláusula aporta tres nodos, uno por cada aparición de un literal, unidos en un triángulo.
• Se pone una arista entre cada par de nodos de cláusulas distintas que tengan literales opuestos, x y ¬x.
• Se pide un conjunto independiente de tamaño k = m.

Elegir un nodo significa “este literal es verdadero, y por él se cumple esta cláusula”. El triángulo dice “a lo sumo uno por cláusula”, de modo que para llegar a m hay que elegir exactamente uno en cada cláusula. La arista entre opuestos dice “no se contradigan”.

algoritmo reducir_a_independiente(formula, m)
    para cada clausula c hacer
        crear tres nodos, uno por literal de c
        unirlos en un triangulo
    fin para
    para cada par de nodos u, v de clausulas distintas hacer
        si literal[u] = no literal[v] entonces
            agregar arista u - v
        fin si
    fin para
    devolver (grafo, m)
fin algoritmo

Un ejemplo seguido en detalle

Tomemos φ = (x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ ¬x3). Tiene m = 3, y cada línea del dibujo es un triángulo:

Fíjense que x3 aparece dos veces, en los nodos 2 y 5. Son nodos distintos y no llevan arista entre sí, porque no se contradicen. Elegir los dos sería coherente.

$ build/is_demo
...
El ejemplo del texto:
(x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ ¬x3)
  nodos: 0:x1 1:x2 2:x3 3:¬x1 4:¬x2 5:x3 6:x1 7:¬x2 8:¬x3
  aristas de literales opuestos: 0-3 1-4 1-7 2-8 3-6 5-8
  k = 3, conjunto independiente máximo: 3 (0:x1, 4:¬x2, 6:x1)
  fuerza bruta sobre la fórmula: satisfacible, x1=V x2=F x3=F
  lectura del conjunto: x1=V x2=F x3=F, ¿cumple? sí

Sigamos la dirección de vuelta. Del conjunto {0, 4, 6} leemos:

x3 no aparece en lo elegido, y entonces su valor da igual. El programa lo deja en F. La asignación x1 = V, x2 = F, x3 = F cumple C0 por x1, C1 por ¬x2 y C2 por x1.

Y la dirección de ida. Otra asignación que cumple φ es x1 = F, x2 = F, x3 = V. Elegimos un literal verdadero en cada cláusula:

{2, 3, 7} tiene tamaño 3 y no tiene aristas adentro. Hay uno por triángulo, y las aristas de opuestos que los tocan son 2-8, 0-3, 3-6 y 1-7, con el otro extremo afuera.

La demostración

Qué se afirma. φ se puede cumplir si y solo si el grafo tiene un conjunto independiente de tamaño m.

Técnica. Dos direcciones, construyendo en cada una la solución del otro lado.

De una asignación a un conjunto. Sea a una asignación que cumple φ. En cada cláusula hay un literal verdadero: elegimos un nodo de cada una con ese literal. Son m nodos. No hay aristas de triángulo entre ellos, porque hay uno por cláusula. No hay aristas entre opuestos, porque todos los elegidos son literales verdaderos bajo a, y x y ¬x no pueden ser los dos verdaderos.

De un conjunto a una asignación. Sea S un conjunto independiente de tamaño m. Cada triángulo tiene a lo sumo un nodo en S, porque sus nodos están unidos, y hay m triángulos. Por lo tanto, S tiene exactamente uno en cada triángulo. Definimos a: para cada nodo de S, su literal es verdadero. Esto no se contradice, porque si S tuviera un nodo con x y otro con ¬x, habría una arista entre ellos. Las variables que S no menciona toman cualquier valor. Cada cláusula tiene un nodo en S, cuyo literal es verdadero, y entonces se cumple. ∎

Tiempo. 3m nodos y a lo sumo 3m + (3m)²/2 aristas. Se construye mirando cada par de nodos.

Con esto, conjunto independiente es NP-completo. Por las reducciones de la semana 13, también lo son cobertura de vértices y clique: los dos están en NP, y conjunto independiente se reduce a ellos.

La pregunta de repaso: dos cláusulas

$ build/is_demo
Dos cláusulas (pregunta de repaso 2):
(x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ ¬x3)
  nodos: 0:x1 1:¬x2 2:x3 3:¬x1 4:x2 5:¬x3
  aristas de literales opuestos: 0-3 1-4 2-5
  k = 2, conjunto independiente máximo: 2 (0:x1, 4:x2)
  fuerza bruta sobre la fórmula: satisfacible, x1=F x2=F x3=F
  lectura del conjunto: x1=V x2=V x3=F, ¿cumple? sí

Son dos triángulos, {0, 1, 2} y {3, 4, 5}, con 3 aristas entre ellos. Hay que elegir uno de cada uno sin que estén unidos, por ejemplo 0 y 4. La fuerza bruta y la lectura dan asignaciones distintas, y eso está bien: la fórmula tiene varias soluciones, y la pregunta es si existe alguna.

Una fórmula sin solución, y aristas de menos

Las ocho cláusulas posibles sobre tres variables no se pueden cumplir: cada asignación falla en justo una. Ahí se ve lo que aporta cada clase de arista:

Sin solución: las ocho cláusulas sobre tres variables.
  24 nodos, 72 aristas, k = 8, máximo: 7

Si faltan aristas, en esa misma fórmula insatisfacible:
  sin literales opuestos: máximo 8, k = 8
  sin triángulos:         máximo 12, k = 8

Sin aristas entre opuestos, se elige un nodo de cada cláusula sin coordinar nada. Sin triángulos, se pueden elegir todos los x1, x2 y x3 positivos, los 12 de ellos, y es fácil pasarse de k. Las dos versiones rompen la misma dirección, la de vuelta: inventan una solución que no existe. La de ida sigue intacta. Es lo mismo que pasaba con una red de flujo mal hecha en la semana 12.

test_examples.cpp compara el máximo con k y con la fuerza bruta en 1500 fórmulas al azar, y comprueba las dos lecturas.

De 3-SAT a 3-coloreo

Un coloreo (coloring) con k colores da un color a cada nodo, de modo que los extremos de cada arista tengan colores distintos. El problema 3-coloreo pregunta si un grafo se puede colorear con tres colores. Sirve para modelar cualquier cosa de “estos dos no pueden ir juntos”: exámenes en franjas horarias, frecuencias de radio, registros de una CPU.

Está en NP: el certificado es el color de cada nodo, y se revisa arista por arista. Es la función is_proper_coloring de graph.h.

En la sección anterior, la reducción tenía una sola pieza repetida. Aquí vamos a construir un circuito. Un gadget es una pieza pequeña de la instancia nueva, diseñada a propósito para portarse como una regla de la instancia original. Necesitamos tres piezas: algo que diga qué es verdadero y falso, algo que represente una variable, y algo que represente un O.

La paleta

Un triángulo con tres nodos, que llamamos T, F y B. Sus tres colores son distintos. Los colores no traen nombre: llamamos color T al que recibe el nodo T, color F al que recibe F, y color B al que recibe B. Así, en cualquier 3-coloreo del grafo, “verdadero” tiene un significado: tener el color de T.

El gadget de variable

Para cada variable x, dos nodos, x y ¬x. Se unen entre sí, y cada uno con el nodo B.

     B
    / \
   x---¬x

x y ¬x no pueden tener el color B, porque están unidos a B. Solo les quedan T y F. Y no pueden tener el mismo, porque están unidos. Entonces, uno tiene T y el otro F. Eso es una asignación, y además una que no se contradice.

La compuerta O

Dos entradas a y b, y tres nodos nuevos p, q, r, con las aristas a-p, b-q, p-q, p-r y q-r. El triángulo p, q, r obliga a usar los tres colores. r es la salida.

   a --- p
         | \
         |  r
         | /
   b --- q

Esta compuerta tiene dos propiedades, las dos se comprueban a mano.

Propiedad 1. Si a y b tienen color F, r tiene color F en todo coloreo. Porque p ≠ F y q ≠ F, por sus aristas con a y b. Pero p, q y r usan los tres colores, y entonces el F le toca a r.

Propiedad 2. Si a o b tiene color T, y las dos tienen color T o F, existe un coloreo de p y q con r de color T. Basta dar:

Cada fila se revisa: p ≠ a, q ≠ b, y p, q, r son distintos. Con a = b = F también hay coloreo, p = T, q = B, r = F, y su r es la que obliga la Propiedad 1.

$ build/coloring_demo
Una compuerta O: qué colores admite la salida r.
  a b | r
  F F | F
  F T | T F B
  T F | T F B
  T T | T

La segunda compuerta puede recibir B, porque r no está unido a B.
  a b | r
  B F | T F B
  B T | T F B

La salida no es un O exacto, porque con una entrada T también admite otros colores. No hace falta más: lo único que necesitamos es “ambas F obliga a F” y “alguna T permite T”. La segunda tabla muestra algo que hay que cuidar. La salida de una compuerta puede tener color B, y al encadenar dos compuertas la segunda puede recibir B. La demostración de abajo lo tiene en cuenta: la dirección de vuelta solo usa la Propiedad 1, que no le importa eso, y la dirección de ida elige siempre T o F.

El gadget de cláusula

Una cláusula (a ∨ b ∨ c) es O(O(a, b), c): dos compuertas encadenadas. A la salida r de la segunda se le ponen aristas a F y a B, y así r queda obligada a tener color T.

Son 6 nodos internos: p₁, q₁, r₁, p₂, q₂, r₂. Con las entradas ya pintadas de T o F, hay 3⁶ = 729 formas de pintarlos. El programa las revisa todas, para cada una de las 8 entradas:

El gadget de cláusula: coloreos de sus 6 nodos internos, de 3^6 = 729 posibles.
  a b c | coloreos
  F F F | 0
  F F T | 2
  F T F | 2
  F T T | 4
  T F F | 2
  T F T | 4
  T T F | 2
  T T T | 4

Lema. Con la paleta y las tres entradas pintadas de T o F, el gadget de cláusula se puede completar si y solo si alguna entrada es T.

Técnica. Se usan las dos propiedades de la compuerta, y la tabla es una comprobación exhaustiva de lo mismo.

Si todas son F, la Propiedad 1 da r₁ = F. Entonces la segunda compuerta también tiene sus dos entradas en F, y da r₂ = F. Pero r₂ está unida a F. Es imposible.

Si alguna es T, pintamos la primera compuerta con su Propiedad 2 si a o b es T, y r₁ = T. Si no, con la coloración p₁ = T, q₁ = B, r₁ = F. Así, r₁ queda en T o F. Como r₁ o c es T, la Propiedad 2 aplicada a la segunda compuerta da r₂ = T, que no choca con sus aristas a F y a B. ∎

La reducción completa

La transformación. Dada una fórmula φ de 3-SAT con n variables y m cláusulas: la paleta, un gadget de variable por cada variable, y un gadget de cláusula por cada cláusula, cuyas entradas son los nodos de sus tres literales. Un nodo de literal se comparte entre todas las cláusulas en que aparece.

Teorema. φ se puede cumplir si y solo si el grafo es 3-coloreable. Y 3-coloreo es NP-completo.

Técnica. Dos direcciones.

De una asignación a un coloreo. Sea a una asignación que cumple φ. Se pintan T, F y B con tres colores. Cada literal verdadero, de T. Cada literal falso, de F. El gadget de variable queda bien: los dos nodos tienen T y F, y ninguno es B. Cada cláusula tiene un literal verdadero, y por el Lema su gadget se completa. Las aristas de un gadget de cláusula solo tocan nodos propios, los de sus entradas y la paleta, y el Lema las revisó todas. Luego el coloreo es propio.

De un coloreo a una asignación. Tomemos un 3-coloreo cualquiera. La paleta usa tres colores distintos, y los llamamos T, F y B, según el nodo que los recibió. Ningún otro nombre es posible, y el grafo no sabe de nombres: este paso es el que permite hablar de “verdadero”. Cada par x, ¬x tiene un T y un F, por el gadget de variable. Definimos x verdadera si el nodo x tiene color T. Eso le da a ¬x su valor correcto. Sea (a ∨ b ∨ c) una cláusula. Sus entradas tienen colores T o F, y el gadget está coloreado. Por el Lema, alguna entrada es T: la cláusula se cumple. ∎

Tiempo. El grafo tiene 3 + 2n + 6m nodos y 3 + 3n + 12m aristas: es lineal en la fórmula.

Fórmulas completas:
(x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ ¬x3)
  21 nodos, 36 aristas
  ¿3-coloreable? sí, fuerza bruta sobre la fórmula: satisfacible
  lectura del coloreo: x1=V x2=V x3=V, ¿cumple? sí
(x1 ∨ x2 ∨ x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ ¬x3)
  27 nodos, 48 aristas
  ¿3-coloreable? sí, fuerza bruta sobre la fórmula: satisfacible
  lectura del coloreo: x1=V x2=V x3=V, ¿cumple? sí
(¬x1 ∨ ¬x2 ∨ ¬x3) ∧ (x1 ∨ ¬x2 ∨ ¬x3) ∧ (¬x1 ∨ x2 ∨ ¬x3) ∧ (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x3)
  57 nodos, 108 aristas
  ¿3-coloreable? no, fuerza bruta sobre la fórmula: insatisfacible

Para hacerse una idea de cómo se vería el circuito, en el gadget de una cláusula (x1 ∨ ¬x2 ∨ x3):

Qué arista hace falta

El programa quita aristas en la fórmula de ocho cláusulas, que no tiene solución:

Si faltan aristas, en la fórmula de ocho cláusulas, que no tiene solución:
  variables sin arista a B:      3-coloreable
  salida sin arista a F:         3-coloreable
  salida sin arista a B:         no 3-coloreable

Las dos primeras rompen la reducción. Sin la arista a B, un literal puede tener color B, y es el truco para que x y ¬x estén “los dos activos”. Sin la arista a F, la salida puede ser F en el caso de tres entradas falsas, y la cláusula deja de decir algo.

La tercera línea llama la atención: la arista de la salida a B no hace falta. La demostración de vuelta solo usó que r₂ ≠ F. Con r₂ = B en un coloreo, alguna entrada de la segunda compuerta no era F, y eso basta. La dejamos porque se lee mejor “la salida tiene color T”, y las pruebas confirman en 60 fórmulas al azar que quitarla no cambia la respuesta. Es el ejercicio 7.

En C++. reduce_to_coloring arma el grafo, find_coloring lo resuelve con backtracking nodo por nodo, y coloring_from_assignment pinta sin buscar, siguiendo la demostración. Las pruebas corren 200 fórmulas, y comprueban que coinciden con la fuerza bruta sobre la fórmula. También comprueban que la lectura funciona con las 6 formas de renombrar los colores: ese es justo el paso de “los llamamos T, F y B”. El backtracking es rápido con estos grafos, porque los nodos están en un buen orden. Eso no dice nada sobre un grafo cualquiera.

De cobertura de vértices a suma de subconjuntos

Hasta aquí los problemas tenían estructura de grafo o de fórmula. Ahora aparecen números.

Definición. En suma de subconjuntos (subset sum), la entrada es una lista de enteros positivos, que pueden repetirse, y un objetivo t. La pregunta es si alguna parte de la lista suma exactamente t. Los números se escriben en binario.

Está en NP: el certificado es la lista de posiciones elegidas. La suma tiene a lo sumo unos pocos bits más que el número más grande, y se calcula en tiempo polinomial. La función sums_to_target es ese verificador.

Vamos a reducir desde cobertura de vértices (vertex cover), de la semana 13: dado un grafo G y un entero k, ¿hay un conjunto de a lo sumo k nodos que toque todas las aristas? Necesitamos escribir un grafo dentro de una suma, y en una suma no hay condiciones lógicas. Lo único que controlamos es qué dígitos salen.

La tabla

Sean V la cantidad de nodos y E la de aristas, numeradas e₀, e₁, y así hasta la última. Si k > V, cambiamos k por V: la respuesta no cambia, porque V nodos ya cubren todo. Los números se escriben en base 4, con un dígito por arista y uno más arriba:

• Número de nodo. Para cada nodo v: un 1 en el dígito de arriba, y un 1 en el dígito de cada arista que toca v.
• Número de holgura. Para cada arista eⱼ: un 1 en el dígito de eⱼ, y nada más.
• Objetivo. El dígito de arriba es k, y cada dígito de arista es 2.

algoritmo reducir_a_suma(grafo, V, E, k)
    k ← mín(k, V)
    para cada nodo v hacer
        numero[v] ← 4^E
        para cada arista j que toca v hacer
            numero[v] ← numero[v] + 4^j
        fin para
    fin para
    para j desde 0 hasta E - 1 hacer
        holgura[j] ← 4^j
    fin para
    t ← k · 4^E
    para j desde 0 hasta E - 1 hacer
        t ← t + 2 · 4^j
    fin para
    devolver (numeros y holguras, t)
fin algoritmo

El significado de cada columna es la clave. La columna de arriba cuenta cuántos nodos se eligieron. Cada columna de arista cuenta cuántos extremos de esa arista se eligieron, más su holgura. Pedir 2 en una columna significa: dos extremos, o un extremo y su holgura. Lo que no se puede lograr es cero extremos, porque la holgura sola da 1. Esa es la condición de cobertura escrita en dígitos.

Veamos un grafo de 4 nodos, con e₀ = 0-1, e₁ = 0-2, e₂ = 1-2 y e₃ = 2-3:

$ build/subset_demo
Grafo de 4 nodos con aristas e0=0-1 e1=0-2 e2=1-2 e3=2-3

La tabla con k = 2, en base 4:
  número     arriba e3 e2 e1 e0   decimal
  nodo 0      1       0  0  1  1   261
  nodo 1      1       0  1  0  1   273
  nodo 2      1       1  1  1  0   340
  nodo 3      1       1  0  0  0   320
  holgura e0  0       0  0  0  1   1
  holgura e1  0       0  0  1  0   4
  holgura e2  0       0  1  0  0   16
  holgura e3  0       1  0  0  0   64
  objetivo    2       2  2  2  2   682

Respuestas:
  k = 0: cobertura mínima de tamaño 2, suma: ninguna elección llega al objetivo 170
  k = 1: cobertura mínima de tamaño 2, suma: ninguna elección llega al objetivo 426
  k = 2: cobertura mínima de tamaño 2, suma: se llega con 273 340 1 4 64
    nodos elegidos: 1 2
  k = 3: cobertura mínima de tamaño 2, suma: se llega con 273 340 320 1 4
    nodos elegidos: 1 2 3
  k = 4: cobertura mínima de tamaño 2, suma: se llega con 261 273 340 320
    nodos elegidos: 0 1 2 3
  k = 5: cobertura mínima de tamaño 2, suma: se llega con 261 273 340 320
    nodos elegidos: 0 1 2 3

Sumemos por columnas la respuesta de k = 2, es decir, los nodos 1 y 2 y las holguras de e₀, e₁ y e₃:

e₂ tiene sus dos extremos elegidos, y no usa holgura. Las otras tres tienen uno, y usan la suya. Fíjense también en k = 5: como el grafo tiene 4 nodos, se usa k = 4.

Por qué no hay acarreos

La suma de los números es una suma de enteros. No hay nada que obligue a sumar “por columnas”: si una columna se pasara de 3, llevaría a la siguiente, y lo que parecía una condición sobre una arista se mezclaría con la de al lado.

No pasa, y por una cuenta simple. En cada columna de arista, entre todos los números de la lista hay exactamente tres 1: los dos extremos y la holgura. Aunque se elijan todos, la columna suma 3, que es menor que 4. Por eso la base es 4. Toda elección da, en cada columna de arista, un valor entre 0 y 3. Y ese valor es exactamente el dígito de la suma, sin llevar nada.

La columna de arriba puede llegar a V, que puede ser más que 3. Eso no molesta, porque no tiene nada por encima que pueda pisar. Es un “dígito” solo en sentido amplio: es el cociente de dividir entre 4^E.

Las pruebas comprueban esto en cada instancia que generan: en cada columna de arista, los dígitos de toda la lista suman exactamente 3.

La demostración

Qué se afirma. G tiene una cobertura de tamaño a lo sumo k si y solo si alguna parte de la lista suma t, con k ≤ V ya ajustado.

Técnica. Dos direcciones, usando la unicidad de la escritura en base 4.

El hecho central. Tomemos cualquier elección de números, con c números de nodo. Sea dⱼ la cantidad de 1 elegidos en la columna eⱼ. Como dⱼ ≤ 3, la suma es c · 4^E + Σ dⱼ · 4^j, y esa parte de abajo es menor que 4^E. Un entero se escribe de una sola forma en base 4. Así que la suma es igual a t si y solo si c = k y dⱼ = 2 para toda arista.

De una cobertura a una elección. Sea C una cobertura de tamaño a lo sumo k. Como k ≤ V, se le pueden agregar nodos hasta tener exactamente k, y sigue siendo cobertura. Elegimos los números de esos k nodos, así que c = k. Cada arista tiene 1 o 2 extremos elegidos. Si tiene 1, elegimos además su holgura. Si tiene 2, no. Ahora dⱼ = 2 en todas, y la suma es t.

De una elección a una cobertura. Sea una elección que suma t. Por el hecho central, tiene k números de nodo, y dⱼ = 2 en cada arista. Sean C esos k nodos. Para una arista eⱼ, los 1 de su columna vienen de sus extremos y de su holgura, que aporta a lo sumo 1. Entonces, al menos uno viene de un extremo: C toca a eⱼ. Luego C es una cobertura de tamaño k. ∎

Tiempo. Hay V + E números, cada uno de a lo sumo 2E + log V + O(1) bits. La entrada de suma de subconjuntos ocupa O((V + E) · (E + log V)) bits, que es polinomial en el tamaño del grafo, y se escribe en ese tiempo.

Conclusión. Suma de subconjuntos es NP-completo.

¿Hace falta la base 4?

Si la base no alcanza, los dígitos se pisan. En base 2, el objetivo ya ni siquiera dice lo que queremos, porque “2” no es un dígito:

En base 2 los dígitos se pisan:
  aristas 0-1 y 2-3, k = 0, cobertura mínima 2
  números: 5 5 6 6 1 2, objetivo 6
  la suma dice sí, con el número 6 (posición 2)

Búsqueda de respuestas falsas en otras bases:
  base 2: hay una respuesta falsa
  base 3: ninguna respuesta falsa en 4000 grafos al azar
  base 4: ninguna respuesta falsa en 4000 grafos al azar

k = 0 es imposible en ese grafo, porque tiene aristas, pero un solo número de nodo ya da el objetivo. El caso de la base 3 es interesante: una columna sí puede sumar 3 y llevar 1, y aun así el programa no encontró ninguna respuesta falsa. Eso no es una demostración, pero el ejercicio 6 pide hacerla, y resulta que la base 3 también sirve. Elegimos 4 porque con ella la demostración no tiene que hablar de acarreos, y el ahorro de usar otra base no cambia nada de lo que interesa.

Por qué tantos dígitos, y por qué O(nW) no contradice nada

En la semana 7 resolvimos este tipo de problema con programación dinámica en O(nW), donde W es el objetivo. Y ahora decimos que es NP-completo. ¿No demuestra eso que P = NP?

No, porque O(nW) no es polinomial en los bits de la entrada: es pseudopolinomial. W se escribe en log W bits, y W vale hasta 2 elevado a esos bits. La reducción aprovecha justamente ese hueco. Cada arista agrega un dígito, de modo que el objetivo crece como 4^E, mientras la entrada solo crece en una cantidad polinomial de bits.

make bench corre la programación dinámica sobre instancias que salen de la reducción, con un ciclo de E aristas (con 2 aristas, un camino):

$ make bench
 aristas   n   bits del objetivo    objetivo W             n·W   entrada en bits   respuesta   segundos
       2   5                   5            26             130                24         sí      0.000
       3   6                   8           170            1020                38         sí      0.000
       4   8                  10           682            5456                62         sí      0.000
       5  10                  12          3754           37540                92         sí      0.000
       6  12                  14         15018          180216               128         sí      0.000
       7  14                  17         76458         1070412               171         sí      0.001
       8  16                  19        305834         4893344               219         sí      0.003
       9  18                  21       1485482        26738676               273         sí      0.017
      10  20                  23       5941930       118838600               333         sí      0.077
      11  22                  25      27962026       615164572               399         sí      0.399
      12  24                  27     111848106      2684354544               471         sí      1.726
      13  26                  29     514501290     13377033540               549         sí      8.650

Los tiempos dependen de la máquina. Se midieron en el contenedor del curso, compilando con -O2, en una sola corrida, así que solo sirven para ver el orden de magnitud. La columna que manda es n·W: de 12 a 13 aristas W se multiplicó por 4,6, con un dígito más y también un k mayor, n·W por 5, y el tiempo por 5. La entrada en bits, en cambio, pasó de 471 a 549. Cada arista más multiplica el trabajo, y solo agrega dos filas y una columna a la tabla.

Eso responde la pregunta de repaso: ¿por qué la reducción necesita números con muchos dígitos? Porque cada arista necesita su propia columna, que no se mezcle con las demás. Y hay una razón más profunda, que no depende de esta construcción en particular. Si alguna reducción desde un problema NP-completo produjera siempre números con W polinomial en el tamaño de la entrada, entonces la programación dinámica correría en tiempo polinomial sobre ellos, y P = NP. Así que, salvo que P = NP, toda reducción de este tipo tiene que producir, al menos en algunas instancias, números cuyo valor no está acotado por un polinomio, aunque se escriban en pocos bits.

Por eso importa que los números vayan en binario. Si la entrada los escribiera en unario, una marca por unidad, la entrada misma ocuparía W símbolos, O(nW) sería polinomial en ella, y este problema estaría en P. Lo difícil de suma de subconjuntos son los números enormes escritos en pocos bits.

Idea clave. O(nW) y “NP-completo” hablan de cosas distintas. La programación dinámica resuelve bien los casos con números pequeños. La NP-completitud dice que, si P ≠ NP, hay casos difíciles, y esos casos tienen números enormes. Ambas cosas son ciertas a la vez.

La mochila

Lo que quedó pendiente desde la semana 7 es ahora una línea.

Definición. La mochila en versión de decisión recibe n objetos con peso y valor, una capacidad W y una meta V. Pregunta si hay objetos cuyo peso total sea a lo sumo W y cuyo valor total sea al menos V.

Teorema. La mochila en versión de decisión es NP-completa.

Está en NP: el certificado son los objetos elegidos. Reducción desde suma de subconjuntos: para cada número x, un objeto con peso x y valor x. Capacidad y meta iguales a t. Las dos direcciones: si una parte suma t, esos objetos pesan t ≤ W y valen t ≥ V. Y si hay objetos con peso a lo sumo t y valor al menos t, como peso y valor son la misma suma, esa suma es exactamente t. Tiempo: lineal. ∎

Con esto, la cadena está completa, de Cook-Levin hasta la mochila:

Las dos flechas que salen de conjunto independiente son de la semana 13, y las demás de esta.

Si mañana alguien resuelve 3-SAT en O(n⁵)

Esta es la pregunta de repaso 5, y es buena porque la respuesta fácil tiene una flecha al revés.

Lo primero es la conclusión: 3-SAT es NP-completo, y entonces P = NP. En particular, la mochila en versión de decisión se resolvería en tiempo polinomial, en los bits de la entrada.

¿Cómo? La cadena de arriba no sirve para esto. Dice que 3-SAT se reduce a la mochila, y eso permitiría resolver 3-SAT con un algoritmo de mochila, no al revés. Lo que hace falta es mochila ≤ₚ 3-SAT, y eso existe por otra razón:

1. La mochila en versión de decisión está en NP.
2. Por Cook-Levin, entonces mochila ≤ₚ SAT.
3. Y SAT ≤ₚ 3-SAT, por lo que vimos hoy.

Se compone todo, y una mochila de s bits se transforma en una fórmula de 3-SAT de tamaño p(s), para algún polinomio p. Se corre el algoritmo y resulta un costo de O(p(s)⁵), más el de transformar. Es polinomial, y este argumento no garantiza O(s⁵). El exponente lo decide el tamaño de la transformación, y p(s) puede ser mucho mayor que s. Por eso, un resultado así cambiaría la teoría de inmediato, y no necesariamente la práctica.

¿Y la versión de optimización, la que devuelve el mejor valor? Se recupera con búsqueda binaria sobre el valor, usando la decisión como caja negra. El óptimo está entre 0 y la suma de los valores. Se pregunta “¿se llega a V?” y se parte el rango. Son a lo sumo ⌈log₂(Σv + 1)⌉ llamadas, que no es más que el número de bits de la entrada, salvo por una constante, porque Σv se escribe en pocos bits. Para saber qué objetos llevar, se pregunta uno por uno si sobra.

$ build/knapsack_demo
objetos (peso, valor): (4, 10) (3, 7) (2, 4) (5, 12) (1, 1)
capacidad 9, suma de valores 34
óptimo por búsqueda binaria: 22, con 5 llamadas a la decisión
óptimo por la tabla de la semana 7: 22
objetos elegidos, con otra llamada por objeto: 0 3
suma de subconjuntos {3, 5, 9} con objetivo 8: mochila dice sí, fuerza bruta dice sí
suma de subconjuntos {3, 5, 9} con objetivo 10: mochila dice no, fuerza bruta dice no

Aquí la caja negra es la tabla de la semana 7, porque es lo que tenemos: el punto es que solo se le hacen preguntas de sí o no. El mismo esquema funciona con cualquier algoritmo de decisión.

Error común. Decir “la mochila se reduce a 3-SAT porque 3-SAT se reduce a la mochila”. Las reducciones no se invierten. Aquí valen las dos, pero por razones distintas: una por la cadena de reducciones, la otra por Cook-Levin.

Un mapa de problemas

Cuando el problema nuevo se ve difícil, ¿desde cuál reducir? Conviene empezar desde el que tenga la misma forma. Las piezas de la transformación salen casi solas, y quedan menos gadgets por inventar.

Lo que hay detrás de esta tabla, y qué tanto se demostró aquí:

Todos los de esa tabla son NP-completos. No todo problema que parece difícil lo es: la siguiente sección tiene cuatro casos en que no.

En la práctica. Antes de buscar una reducción, vale la pena intentar un algoritmo durante un rato. Si cada decisión obliga a la siguiente, puede ser un caso de la frontera. Si al intentarlo siempre reaparece “hay que probar todas las combinaciones”, conviene buscar la reducción. Es una orientación, no una prueba: lo que decide es la demostración.

Cerca de la frontera

Pequeños cambios en el enunciado separan lo fácil de lo difícil. Estos cuatro pares aparecen en todas partes, y vale la pena tener claro por qué caen de cada lado.

2-SAT: las cláusulas son implicaciones

Una fórmula de 2-SAT tiene cláusulas de dos literales, que pueden tener la misma variable: (x ∨ x) y (x ∨ ¬x) se permiten.

La clave es que (a ∨ b) significa dos cosas: si a es falso, b tiene que ser verdadero, y si b es falso, a tiene que ser verdadero. Con tres literales esto no pasa: que a sea falso solo deja una alternativa entre dos. Con dos, una decisión obliga a otra, y una cadena de obligaciones es un camino en un grafo.

Definición. El grafo de implicaciones (implication graph) de una fórmula con n variables tiene 2n nodos, uno por literal. Cada cláusula (a ∨ b) aporta dos aristas: ¬a → b y ¬b → a.

Las dos aristas son la misma regla, leída de dos maneras. Una asignación cumple (a ∨ b) si y solo si en ninguna de esas dos aristas el origen es verdadero y el destino es falso. Y como esto vale para cada arista, una asignación que cumple la fórmula no puede tener un camino de un literal verdadero hacia un literal falso: en algún punto del camino, una arista haría esa transición.

Las cláusulas raras no necesitan un trato especial. (x ∨ x) da dos veces ¬x → x: “si x es falsa, x es verdadera”, lo que solo se cumple con x verdadera. (x ∨ ¬x) da x → x y ¬x → ¬x, dos lazos que no restringen nada.

algoritmo dos_sat(formula)
    construir el grafo de implicaciones
    comp ← componentes(grafo)
    para cada variable x hacer
        si comp[x] = comp[no x] entonces
            devolver "no se puede"
        fin si
        valor[x] ← comp[x] < comp[no x]
    fin para
    devolver valor
fin algoritmo

componentes es Kosaraju-Sharir, exactamente como en la semana 6: DFS sobre el grafo invertido, y recorrido del original en orden decreciente de fin. Recordemos una propiedad que se demostró allá: las componentes salen de sumidero a fuente. Se numeran 0, 1, 2… en ese orden, y entonces toda arista u → v entre componentes distintas cumple comp[u] > comp[v]. Si u y v están en la misma, comp[u] = comp[v]. En resumen, toda arista u → v cumple comp[u] ≥ comp[v].

Teorema. La fórmula se puede cumplir si y solo si ninguna variable x tiene a x y ¬x en la misma componente. Además, si es así, dos_sat devuelve una asignación que la cumple.

Técnica. Una dirección por el camino de implicaciones. La otra, con una cadena de desigualdades sobre comp.

Si x y ¬x están en la misma componente, no hay solución. Hay un camino de x a ¬x y otro de ¬x a x. En cualquier asignación, uno de los dos literales es verdadero y el otro falso, y uno de esos caminos iría de verdadero a falso, cosa que no se permite en una asignación que cumple la fórmula.

Si ninguna variable tiene ese problema, la asignación funciona. Primero, está bien definida: como comp[x] ≠ comp[¬x], un literal y su negación reciben valores opuestos. En palabras: un literal ℓ es verdadero si y solo si comp[ℓ] < comp[¬ℓ].

Supongamos que una cláusula (a ∨ b) no se cumple, es decir, a y b son falsos. Por la regla, comp[a] > comp[¬a] y comp[b] > comp[¬b]. Las aristas ¬a → b y ¬b → a dan comp[¬a] ≥ comp[b] y comp[¬b] ≥ comp[a]. Juntando todo:

comp[a] > comp[¬a] ≥ comp[b] > comp[¬b] ≥ comp[a]

Eso dice que comp[a] > comp[a]. Es una contradicción, y cubre también los casos raros: con a = b, y con b = ¬a, la cadena es la misma. Entonces toda cláusula se cumple. ∎

Costo. 2n nodos y 2m aristas, de modo que Kosaraju-Sharir da Θ(n + m). 2-SAT se resuelve en tiempo lineal.

La intuición de la regla: un literal verdadero arrastra a todo lo que se alcanza desde él, así que conviene que lo verdadero esté lo más cerca posible de los sumideros, para arrastrar lo menos posible. Y es justo lo que dice comp[ℓ] < comp[¬ℓ], porque las componentes salen de sumidero a fuente.

$ build/two_sat_demo
(x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3) ∧ (¬x3 ∨ ¬x1)
  aristas: x1→x3 x1→¬x3 ¬x1→x2 x2→¬x3 ¬x2→x1 x3→¬x2 x3→¬x1 ¬x3→¬x1
  componentes, en el orden en que salen (de sumidero a fuente): {¬x1 x2 ¬x3} {x1 ¬x2 x3}
  x verdadera si comp[x] < comp[¬x]: x1=F x2=V x3=F, ¿cumple? sí
  con el orden al revés:            x1=V x2=F x3=V, ¿cumple? no

(x1 ∨ x2) ∧ (¬x2 ∨ x3) ∧ (¬x3 ∨ x4)
  aristas: ¬x1→x2 x2→x3 ¬x2→x1 x3→x4 ¬x3→¬x2 ¬x4→¬x3
  componentes, en el orden en que salen (de sumidero a fuente): {x4} {x3} {x2} {¬x1} {x1} {¬x2} {¬x3} {¬x4}
  x verdadera si comp[x] < comp[¬x]: x1=F x2=V x3=V x4=V, ¿cumple? sí
  con el orden al revés:            x1=V x2=F x3=F x4=F, ¿cumple? sí

(x1 ∨ x2) ∧ (x1 ∨ ¬x2) ∧ (¬x1 ∨ x2) ∧ (¬x1 ∨ ¬x2)
  aristas: x1→x2 x1→¬x2 ¬x1→x2 ¬x1→¬x2 x2→x1 x2→¬x1 ¬x2→x1 ¬x2→¬x1
  componentes, en el orden en que salen (de sumidero a fuente): {x1 ¬x1 x2 ¬x2}
  x1 y su negación en la misma componente
  x2 y su negación en la misma componente
  insatisfacible; fuerza bruta: insatisfacible

Cláusulas raras: (x1 ∨ x1) obliga a x1, y (x2 ∨ ¬x2) no dice nada.
(x1 ∨ x1) ∧ (x2 ∨ ¬x2)
  aristas: ¬x1→x1 ¬x1→x1 x2→x2 ¬x2→¬x2
  componentes, en el orden en que salen (de sumidero a fuente): {¬x2} {x2} {x1} {¬x1}
  x verdadera si comp[x] < comp[¬x]: x1=V x2=F, ¿cumple? sí
  con el orden al revés:            x1=F x2=V, ¿cumple? no

Con una sola arista por cláusula, en la fórmula insatisfacible:
  ¿x y ¬x en la misma componente? no

Sigamos el primer caso. Hay dos componentes, {¬x1, x2, ¬x3} primero y {x1, ¬x2, x3} después. Hay una arista x1 → ¬x3 entre ellas, que va de la segunda a la primera, como se esperaba. La regla da verdadero a los literales de la primera, es decir ¬x1, x2 y ¬x3: x1 = F, x2 = V, x3 = F. Las cuatro cláusulas se cumplen. Con el orden al revés, se elige la otra componente, que tiene x1 y x3 verdaderas, y falla en (¬x3 ∨ ¬x1). En el segundo caso, por casualidad, el orden al revés también cumple la fórmula: un error así puede pasar varias pruebas. En el último caso falla sin vueltas: x1 tiene que ser verdadera, y el orden al revés la deja en falso.

Error común. Tomar la regla de memoria, sin revisar qué orden da su algoritmo de componentes. Con la versión de la semana 6 las componentes salen de sumidero a fuente, y la regla es comp[x] < comp[¬x]. La versión de CLRS, que saca el orden del grafo original, las da en el otro sentido, y ahí la comparación se invierte. Lo que no cambia es el principio: gana el literal más cercano a los sumideros.

Error común. Agregar solo una arista por cláusula. Las dos aristas son la misma regla, y la demostración usa las dos. En la última línea de la salida, sin la segunda arista, la fórmula insatisfacible parece no tener problema.

En C++. two_sat.h usa un DFS recursivo, porque aquí las fórmulas son pequeñas. Con cientos de miles de variables, los caminos pueden ser muy largos, y esa recursión agota la pila. La semana 6 mostró el problema, y cómo se resuelve con una pila explícita. El laboratorio pide justamente esos tamaños.

Las pruebas corren 6000 fórmulas de 2-SAT al azar, con (x ∨ x) y (x ∨ ¬x) incluidas. Comprueban que toda arista cumple comp[u] ≥ comp[v], que la condición de la misma componente coincide con la fuerza bruta, y que la asignación de la regla cumple la fórmula. También comprueban que en algunas de esas fórmulas el orden al revés falla, y la versión con una sola arista se equivoca.

2-coloreo: un color obliga a los vecinos

Con dos colores no hay nada que elegir después del primer nodo: cada vecino queda obligado al color contrario. Un BFS pinta cada componente del grafo por capas, y falla si y solo si encuentra una arista entre dos nodos del mismo color. Eso pasa si y solo si el grafo tiene un ciclo de largo impar. Cuesta Θ(V + E).

Es lo mismo que en 2-SAT: una decisión obliga a otra. De hecho, 2-coloreo se puede escribir como una fórmula de 2-SAT, con una variable por nodo y dos cláusulas por arista, que dicen “son distintos”. Con tres colores, el nodo vecino todavía tiene dos opciones, y nada queda obligado. Ahí está el salto.

Ciclo euleriano: los grados bastan

Un ciclo euleriano recorre cada arista exactamente una vez, y puede repetir nodos. Un ciclo hamiltoniano recorre cada nodo exactamente una vez. Se escriben casi igual.

Teorema. Un grafo tiene un ciclo euleriano si y solo si todos sus nodos tienen grado par, y todas sus aristas están en una sola componente.

Es necesario. Cada vez que el ciclo entra a un nodo también sale, de modo que usa sus aristas de a dos. Y un solo ciclo no puede saltar entre componentes.

Es suficiente. Partimos de un nodo con aristas y caminamos sin repetir aristas hasta atascarnos. Como todos los grados son pares, solo podemos atascarnos en el nodo de partida: cada otro nodo al que entramos deja una arista libre para salir. Si quedan aristas sin usar, por la conexión alguna toca un nodo del ciclo. Desde ahí se saca otro ciclo con lo que queda, donde los grados siguen siendo pares, y se empalma. Se repite hasta usar todas. ∎

Decidirlo cuesta Θ(V + E). La condición de conexión es la parte que se olvida:

$ build/frontier_demo
Camino más largo en un DAG de 6 nodos: 3 aristas, fuerza bruta 3
2-coloreo: triángulo no (3 colores: sí), cuadrado sí
¿Ciclo que use cada arista exactamente una vez?
  dos triángulos con un nodo común: grados y conexión sí, fuerza bruta sí
  dos triángulos separados        : grados y conexión no, fuerza bruta no
  triángulo con una cola          : grados y conexión no, fuerza bruta no
Camino simple más largo, y camino hamiltoniano:
  cuadrado: 3 aristas, de V − 1 = 3: hamiltoniano
  estrella: 2 aristas, de V − 1 = 3: no hamiltoniano
2-SAT: (x1 ∨ x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3): x1=F x2=V x3=F

Dos triángulos separados tienen todos los grados pares, y no tienen un ciclo euleriano. Para el camino euleriano se pide la misma conexión, con 0 o 2 nodos de grado impar.

La diferencia de fondo es que la condición de Euler es casi local: cada nodo revisa su grado, y solo falta comprobar la conexión con un recorrido. Para Hamilton no se conoce nada así. Las aristas sobran o faltan según lo que hagan las demás, y ciclo hamiltoniano es NP-completo.

Camino más largo: el orden lo cambia todo

En un DAG, el camino más largo se resuelve con programación dinámica sobre el orden topológico, como en la semana 9: L(u) depende solo de los sucesores de u, que ya se calcularon. Es Θ(V + E).

En un grafo general, pedimos un camino simple, sin repetir nodos, porque si no, cualquier ciclo se podría dar vueltas sin fin. Y es difícil, por una reducción de una línea desde camino hamiltoniano: un grafo con V nodos tiene un camino hamiltoniano si y solo si su camino simple más largo tiene V − 1 aristas. Esa es la reducción que se ve en el cuadrado y la estrella de arriba.

¿Por qué no sirve la misma recurrencia? Porque el resultado de L(v) depende de qué nodos ya usó el camino. El subproblema tendría que recordar ese conjunto, y volvemos a Held-Karp de la semana 10, con sus 2ⁿ estados. El DAG no tiene ese problema: lo que ya se usó nunca se puede volver a alcanzar.

La pregunta de repaso 4

La tercera engaña a muchos, porque suena a Hamilton. Lean si dice “cada arista” o “cada nodo”.

NP-completo no quiere decir irresoluble

Error común. Decir “es NP-completo, así que no se puede resolver”. Sí se puede. Hay un algoritmo, y con frecuencia funciona muy bien. Lo que no se conoce es uno que garantice ser rápido en todos los casos.

Esto se ve con un experimento. make solver genera fórmulas de 3-SAT al azar, con unas 4,26 cláusulas por variable, y se las pasa a minisat, el solucionador de la semana 13. Elegimos esa proporción porque con ella las fórmulas al azar salen a veces satisfacibles y a veces no, como se ve en la tabla.

$ make solver
bash solver_runs.sh
 variables cláusulas  semilla        resultado     segundos
       100        426        1   insatisfacible      0.00222
       100        426        2   insatisfacible     0.001628
       100        426        3   insatisfacible     0.001372
       150        639        1   insatisfacible     0.016347
       150        639        2   insatisfacible     0.016048
       150        639        3     satisfacible     0.004653
       200        852        1   insatisfacible     0.066325
       200        852        2   insatisfacible     0.123686
       200        852        3   insatisfacible     0.176462
       250       1065        1   insatisfacible       2.0583
       250       1065        2     satisfacible     0.081472
       250       1065        3   insatisfacible      3.35958
       300       1278        1     satisfacible      3.97467
       300       1278        2   insatisfacible      9.69586
       300       1278        3     satisfacible      1.28771

El principio del palomar: una paloma más que huecos.
    huecos  variables cláusulas        resultado     segundos
         7         56        204   insatisfacible     0.027281
         8         72        297   insatisfacible     0.240779
         9         90        415   insatisfacible      2.38231
        10        110        561     más de 30 s            -

Los tiempos son los que reporta minisat, en el contenedor del curso, y dependen de la máquina. Hay cuatro cosas para ver. Con 300 variables hay 2³⁰⁰ asignaciones, más de 10⁹⁰, y aun así respondió en segundos: el solucionador no las prueba una por una. Respondió también en casos insatisfacibles, donde tiene que descartarlas todas. Los tiempos crecen rápido, y varían mucho entre fórmulas del mismo tamaño: de 250 a 300 variables el peor pasó de unos 3 a unos 10 segundos.

Y la última es la segunda tabla. El principio del palomar dice que n + 1 palomas no caben en n huecos si cada hueco admite una sola. Ustedes lo ven a simple vista, y la fórmula tiene apenas 110 variables con 10 huecos. Aun así, minisat no terminó en los 30 segundos que le dimos, cuando con 9 huecos tardó unos 2 segundos y con 300 variables al azar menos de 10. El tamaño no predice la dificultad. Esto es lo que se espera de un problema NP-completo: funciona muy bien muchas veces, sin garantía para todas.

Por eso, cuando un problema resulta NP-completo, las preguntas útiles son otras. ¿La entrada es pequeña? ¿Tiene una estructura especial? ¿Sirve una respuesta cercana? ¿Lo resuelve un solucionador? Eso es el tema de la semana 15.

El código de la semana

En code/week-14:

Las pruebas se compilan con -g -fsanitize=address,undefined. Las mediciones van con -O2 y sin sanitizers.

$ make test
mkdir -p build
g++ -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined test_examples.cpp -o build/test_examples
build/test_examples
Todas las pruebas de la semana 14 pasaron.

Estas pruebas comprueban, entre otras cosas, lo siguiente:

• En SAT a 3-SAT: 1500 fórmulas con cláusulas de hasta 7 literales, repetidos y x ∨ ¬x. La salida tiene la forma pedida, respeta las cotas de tamaño y es equisatisfactible. Las dos lecturas funcionan. La cláusula vacía da algo insatisfacible.
• En conjunto independiente: 1500 fórmulas, contra la fuerza bruta. Las ocho cláusulas dan máximo 7, y sin alguna clase de aristas la respuesta sale falsa.
• En 3-coloreo: los 8 casos del gadget, 200 fórmulas, y las 6 formas de renombrar los colores. El tamaño del grafo es el que dice el texto. Quitar la arista de variable a B o de salida a F da una respuesta falsa.
• En suma de subconjuntos: 400 grafos pequeños, con k de 0 a V + 2. En cada columna de arista los dígitos suman 3. La suma coincide con la cobertura mínima, con fuerza bruta y con programación dinámica. También se revisa la base 3, y que la base 2 da una respuesta falsa.
• En la mochila: 1500 instancias. La búsqueda binaria da el óptimo de la tabla, en a lo sumo ⌈log₂(Σv + 1)⌉ llamadas, y los objetos elegidos valen eso.
• En 2-SAT: 6000 fórmulas, como se dijo arriba.
• En la frontera: 2-coloreo contra backtracking, Euler contra una búsqueda exhaustiva del ciclo, y DAG contra una búsqueda exhaustiva de caminos, en miles de grafos al azar.
• El complemento de la semana 13: conjunto independiente máximo más cobertura mínima da V, en 500 grafos.

Son pruebas de que los programas hacen lo que dicen, y no reemplazan a las demostraciones.

El laboratorio

La sesión de laboratorio de esta semana es para la Práctica 4. El problema queda como ejercicio opcional, en lab/two_sat. Se trata de asignar turnos a secciones de laboratorio cumpliendo una lista de pedidos, y un verificador revisa el horario.

cd lab/two_sat
make test

El esqueleto lee la entrada y responde siempre NO, de modo que da WA en la mayoría de los casos. Lean los límites antes de empezar. No toda forma de recorrer un grafo los aguanta.

Resumen

• NP-difícil: todo problema de NP se reduce a él. NP-completo: además está en NP.
• Si un NP-difícil está en P, entonces P = NP. Para un NP-completo vale también el recíproco, y todos caen juntos. Para los NP-difíciles fuera de NP, no: la parada es indecidible, y no estaría en P aunque P = NP. La versión de optimización de un problema se llama NP-difícil en un sentido más amplio.
• Cook-Levin, enunciado: SAT en CNF es NP-completo. Es el punto de partida, y se demuestra en Teoría de la Computación.
• La receta: está en NP; elegir uno conocido; transformar del conocido hacia el nuevo; dos direcciones; tiempo polinomial. Olvidar “está en NP” es el error común.
• SAT a 3-SAT: aquí 3-SAT es exactamente tres literales de variables distintas. Se limpia, se rellena lo corto con variables nuevas y se parte lo largo en una cadena donde yⱼ dice “está más adelante”. La salida es equisatisfactible, no equivalente.
• 3-SAT a conjunto independiente: un triángulo por cláusula, aristas entre opuestos, y k igual a las cláusulas. Exactamente uno por triángulo.
• 3-SAT a 3-coloreo: paleta T, F, B; x y ¬x unidos entre sí y a B; dos compuertas O por cláusula y la salida obligada a T. Lo que importa de la compuerta: ambas F obliga a F, y alguna T permite T. Para leer el coloreo, primero se nombran los colores por la paleta.
• Cobertura de vértices a suma de subconjuntos: en base 4, un dígito por arista y uno arriba que cuenta nodos. El objetivo pide 2 en cada arista. En cada columna hay solo tres 1, y por eso no hay acarreos. k se ajusta a mín(k, V), porque la cobertura es “a lo sumo k” y la suma pide “exactamente k”.
• O(nW) no contradice nada: es pseudopolinomial. W crece como 4^E, con una entrada polinomial en bits. Si los números fueran pequeños en valor, el problema estaría en P.
• La mochila en versión de decisión es NP-completa, con peso igual a valor. La optimización sale con búsqueda binaria sobre el valor.
• Si 3-SAT estuviera en O(n⁵): P = NP, y la mochila es polinomial, por Cook-Levin. El exponente lo dicta el tamaño de las reducciones, y no tiene por qué ser 5.
• La frontera: 2-SAT es fácil porque sus cláusulas son implicaciones; 2-coloreo, porque un color obliga al vecino; Euler, por los grados y la conexión; camino más largo en un DAG, por el orden topológico.
• 2-SAT: hay solución si y solo si x y ¬x nunca están en la misma componente. Con las componentes de sumidero a fuente, x es verdadera si comp[x] < comp[¬x].
• NP-completo no significa irresoluble. Significa que no se conoce un algoritmo con garantía polinomial en todos los casos. Un solucionador resolvió aquí fórmulas al azar de 300 variables en segundos, y no pudo en 30 segundos con un palomar de 110.

Ejercicios

1. A mano. Apliquen SAT a 3-SAT a (x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x5) ∧ (x2) ∧ (¬x1 ∨ x3). Den una asignación que cumpla la entrada, y extiéndanla a las variables nuevas con la regla i ≥ j + 2. Comparen con to_three_sat y extend_assignment.
2. El grafo. Dibujen el grafo de conjunto independiente para (x1 ∨ x2 ∨ ¬x3) ∧ (¬x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ ¬x2 ∨ x3). Encuentren un conjunto de tamaño 3, léanlo como asignación y comprueben las tres cláusulas.
3. ¿Está en NP? Para cada problema, digan cuál es el certificado o por qué no se conoce uno: 3-coloreo; “¿este grafo no es 3-coloreable?”; “¿tiene esta fórmula al menos dos soluciones?”; el problema de la parada. Digan cuáles están en NP, cuál no lo está, y de cuál no se sabe.
4. La cadena, otra vez. Demuestren sin mirar las dos direcciones de la cadena para una cláusula de 4 literales. Muestren con un ejemplo por qué las variables nuevas no se pueden compartir: den una fórmula con dos cláusulas de 4 literales y algunas de un literal tal que, usando la misma y en las dos cadenas, la salida quede insatisfacible y la entrada no.
5. Más colores. Demuestren que 4-coloreo es NP-completo, reduciendo desde 3-coloreo con un nodo nuevo unido a todos. Revisen las dos direcciones. Escriban la reducción y compárenla con find_coloring en grafos pequeños.
6. La base 3. Demuestren que la reducción a suma de subconjuntos también es correcta en base 3. Pista: miren la columna más baja, que no recibe acarreos. Su suma es un número de 0 a 3 y debe terminar en 2. Sigan por inducción hacia arriba. ¿Dónde falla este argumento en base 2?
7. Una arista de más. Demuestren que en el gadget de cláusula se puede quitar la arista de la salida a B, y la reducción sigue siendo correcta. Expliquen por qué no se puede quitar la de la salida a F. Compruébenlo con GadgetOptions en la fórmula de ocho cláusulas.
8. Partición. En partición, se pregunta si una lista de números se puede dividir en dos partes de igual suma. Demuestren que es NP-completo, reduciendo desde suma de subconjuntos. Si la suma de la lista es S y el objetivo es t, agreguen dos números bien elegidos. Revisen las dos direcciones, incluido t > S. Programen la reducción y compárenla con la fuerza bruta de subset_sum.h.
9. Cobertura de conjuntos. Dada una familia de conjuntos y un entero k, se pregunta si k de ellos cubren la unión de todos. Demuestren que es NP-completo, reduciendo desde cobertura de vértices. Con esto, ¿cómo queda la tabla del mapa de problemas?
10. Un clique directo. Escriban la reducción de 3-SAT a clique sin pasar por conjunto independiente: nodos por literal, aristas entre nodos de cláusulas distintas que no se contradicen, y k = m. Demuestren las dos direcciones. Comprueben con código que este grafo es el complemento del de reduce_to_independent_set y comparen con max_independent_set sobre el complemento.
11. 2-SAT a mano. Dibujen el grafo de implicaciones de (x1 ∨ x2) ∧ (¬x2 ∨ x3) ∧ (¬x3 ∨ ¬x1) ∧ (x1 ∨ x3). Encuentren las componentes con Kosaraju-Sharir, numeren de sumidero a fuente y lean la asignación. Comparen con two_sat_demo, cambiando la fórmula. Muestren una fórmula donde leer al revés falle, distinta de las del texto.
12. Fácil o difícil. Clasifiquen cada uno, con una reducción o un algoritmo. (a) Dado un grafo, ¿tiene un camino euleriano? (b) Dada una fórmula con cláusulas de dos literales y una cláusula de tres, ¿se cumple? Pista: prueben las tres opciones de esa cláusula. (c) ¿Es 2-coloreable un grafo después de borrar a lo sumo k aristas, con k fijo igual a 1? (d) En un DAG con pesos que pueden ser negativos, ¿hay un camino de peso al menos L? (e) Dada una fórmula cuyas cláusulas tienen dos o tres literales, sin límite de cuántas de tres, ¿se cumple? Si un inciso es difícil, digan desde cuál problema reducirían. Si no, den el costo.