Reducciones entre problemas

Una reducción es traducir: convertir las instancias de un problema en instancias de otro, de modo que la respuesta se conserve. Suena burocrático y es la técnica con la que se demuestra que algo es NP-completo y, al mismo tiempo, la forma más rentable de resolver un problema nuevo.

Qué es reducir, exactamente

Reducir $A$ a $B$ es dar una transformación en tiempo polinomial que lleva cada instancia de $A$ a una de $B$ con la misma respuesta. Se escribe $A \le_p B$ y se lee: $A$ no es más difícil que $B$.

La dirección es la parte que más se confunde. Si $A \le_p B$ y $B$ es fácil, entonces $A$ es fácil. Contrapuesto: si $A$ es difícil, entonces $B$ es difícil. La flecha va del problema conocido al problema del que se quiere hablar.

Los dos pasos de una prueba de NP-completitud

Para probar que un problema $X$ es NP-completo hacen falta dos pasos. Primero, verificar que $X$ está en NP: describir el certificado y cómo se chequea en tiempo polinomial. Ese paso se olvida seguido y sin él la demostración no cierra.

Segundo, elegir un problema NP-completo conocido y reducirlo a $X$. No al revés: reducir $X$ a SAT no prueba nada sobre la dificultad de $X$, sólo que no es peor que SAT.

De 3-SAT a conjunto independiente

Un ejemplo concreto: de 3-SAT a conjunto independiente. Por cada cláusula de tres literales se arma un triángulo de tres vértices, y se conectan entre sí todos los pares de vértices que representan un literal y su negación.

Existe un conjunto independiente de tamaño igual a la cantidad de cláusulas si y sólo si la fórmula es satisfacible: elegir un vértice por triángulo equivale a elegir qué literal hacer verdadero en cada cláusula, y las aristas entre opuestos impiden asignaciones contradictorias. La construcción es polinomial y la equivalencia se prueba en las dos direcciones.

Las tres obligaciones de toda reducción

Toda reducción tiene tres obligaciones. Que la transformación sea polinomial; que una respuesta afirmativa del original dé una afirmativa del traducido; y la vuelta, que una afirmativa del traducido implique una del original.

La tercera es donde fallan las demostraciones apuradas. Es fácil traducir hacia adelante y no darse cuenta de que el problema traducido admite soluciones que no corresponden a ninguna solución del original.

Dada vuelta, es una herramienta de ingeniería

Dada vuelta, la reducción es una herramienta de ingeniería. En vez de escribir un algoritmo para un problema nuevo, se lo traduce a uno con resolvedores maduros: SAT, programación lineal entera, flujo máximo.

Programar horarios, asignar turnos o verificar configuraciones se modelan como SAT y se resuelven con herramientas que llevan décadas de optimización. Escribir la traducción suele ser más rápido y más confiable que escribir el algoritmo propio, aunque el modelo tape parte de la estructura del problema.

El mismo mecanismo en computabilidad

La idea excede a NP. En computabilidad se usa el mismo mecanismo para probar que un problema es indecidible: reduciendo el problema de la parada a él. Si se pudiera resolver, se resolvería la parada, que ya se sabe imposible.

Cambia la clase de recursos y el problema base; la forma del argumento es idéntica.

La reducción como herramienta de todos los días

La reducción se enseña como herramienta teórica —para probar que algo es difícil— y en el trabajo se usa al revés, para resolver: si tu problema se puede expresar como uno conocido, heredás todos sus algoritmos, sus bibliotecas y sus décadas de optimización.

Cierre

Una reducción traduce instancias conservando la respuesta. Para demostrar dificultad se reduce lo conocido-difícil al problema nuevo, nunca al revés, y se prueban las dos direcciones. Para resolver, se reduce lo nuevo a un problema con buenos resolvedores.