GUÍA 30-09-26 Teoría de la Computación

NE111 · miércoles 30/09/2026 · 16:00-17:15 · Sesión 15

NP-completitud · SAT y el teorema de Cook-Levin

REDUCCIÓN POLINOMIAL

A ≤ₚ B si existe una transformación computable en tiempo polinomial que convierte instancias de A en instancias de B preservando la respuesta. Es la misma idea de la sesión 13, ahora con restricción de tiempo.

NP-COMPLETO

Un problema B es NP-completo si está en NP y todo problema de NP se reduce polinomialmente a él. Son los problemas más difíciles de NP.

• Si algún NP-completo estuviera en P, entonces P = NP en su totalidad.
• Si algún problema de NP no está en P, entonces ningún NP-completo lo está.

TEOREMA DE COOK-LEVIN

SAT es NP-completo. Fue el primero que se demostró, y la técnica consistió en codificar el cómputo completo de una máquina de Turing no determinista como una fórmula booleana que es satisfacible si y solo si la máquina acepta.

Esa demostración es la que abre la puerta: una vez que se tiene un problema NP-completo, los demás se prueban por reducción desde él, sin volver a razonar sobre máquinas.

CÓMO SE PRUEBA QUE ALGO ES NP-COMPLETO

1. Mostrar que está en NP exhibiendo un certificado verificable en tiempo polinomial.

2. Tomar un problema ya conocido como NP-completo.

3. Reducirlo polinomialmente al problema nuevo.

Otra vez la dirección importa: se reduce el conocido al nuevo.

LA FAMILIA

SAT, 3-SAT, clique, cubierta de vértices, conjunto independiente, coloreo, mochila, agente viajero, ciclo hamiltoniano, partición. Son miles de problemas de áreas muy distintas, y todos equivalentes: resolver uno rápido los resuelve todos rápido.

QUÉ HACER CON UN PROBLEMA NP-COMPLETO

• Algoritmos de aproximación con garantía de calidad demostrada.
• Heurísticas y metaheurísticas, sin garantía pero buenas en la práctica.
• Explotar la estructura del caso concreto: muchas instancias reales son fáciles.
• Aceptar tiempo exponencial cuando n es pequeño; los resolvedores SAT modernos manejan instancias enormes.

CIERRE DEL BLOQUE

Con esto se cierran las dos preguntas de los límites: qué no se puede computar y qué no se puede computar rápido. A partir de la próxima sesión bajamos a los modelos restringidos, que son los que sí se pueden implementar y son la base de los compiladores.

EJERCICIO

Reducir 3-SAT a cubierta de vértices y verificar que la transformación es polinomial.