P, NP y qué significa NP-completo
NP no quiere decir 'no polinomial' ni 'imposible': quiere decir que una solución propuesta se puede verificar rápido. La pregunta abierta es si verificar rápido implica encontrar rápido.
Para este tema conviene tener claro:Complejidad algorítmica, visualmente
“Ese problema es NP” se usa como sinónimo de “es imposible”, y las dos partes de la frase están mal. NP es una clase de problemas fáciles de verificar, y la mayoría de los que importan están ahí, incluidos los que resolvemos todos los días.
Las clases se definen sobre problemas de sí o no
Las clases se definen sobre problemas de decisión: los que se responden con sí o no. “¿Existe una ruta de costo menor a ?” en vez de “¿cuál es la ruta más barata?”.
No es una limitación real. Si se puede responder la versión de decisión rápido, se puede encontrar el valor óptimo con búsqueda binaria sobre , y de ahí reconstruir la solución. La restricción existe para que la teoría sea manejable.
Antes de seguir, predecí
P es resolver rápido; NP, verificar rápido
P son los problemas que se pueden resolver en tiempo polinomial: ordenar, caminos mínimos, emparejamiento, flujo máximo.
NP son aquellos donde, si alguien propone una solución, se puede verificar en tiempo polinomial. Para el viajante: dada una ruta, sumar sus costos y compararla con es inmediato. Todo problema de P está en NP —resolverlo es una forma de verificarlo—, y la pregunta abierta, con un millón de dólares encima, es si NP está contenido en P.
La asimetría entre encontrar y verificar
Lo que hace interesante a la pregunta es la asimetría entre encontrar y verificar, que en la vida cotidiana damos por obvia. Reconocer una buena demostración es más fácil que escribirla; verificar una clave es más fácil que adivinarla.
Si P fuese igual a NP, esa asimetría no existiría: todo lo verificable sería construible con esfuerzo comparable. Buena parte de la criptografía de clave pública depende de que no sea así.
| Orden | Operaciones | A mil millones por segundo | Dónde aparece |
|---|---|---|---|
| O(n) | 25 | 25 ns | Recorrer una lista |
| O(n²) | 625 | 625 ns | Comparar todos contra todos |
| O(n³) | 15.625 | 16 µs | Multiplicar matrices, ingenuo |
| O(2ⁿ) | 33.554.432 | 34 ms | Probar todos los subconjuntos |
Los NP-completos: todos son el mismo problema
Dentro de NP hay problemas máximamente difíciles: los NP-completos. Un problema lo es si está en NP y cualquier otro problema de NP se le puede reducir en tiempo polinomial.
Eso implica algo fuerte: un algoritmo polinomial para uno solo de ellos resolvería todos. Cook y Levin probaron que SAT —decidir si una fórmula booleana puede satisfacerse— es uno, y desde ahí la lista creció por reducciones sucesivas: 3-SAT, coloreo de grafos, clique, mochila, viajante, conjunto independiente.
NP-difícil y NP-completo no son sinónimos
Conviene separar dos etiquetas que se confunden. NP-difícil es “al menos tan difícil como cualquier problema de NP”, sin exigir estar en NP: incluye problemas de optimización y también problemas mucho peores, como el halting problem, que directamente no son decidibles.
NP-completo es la intersección: NP-difícil y además en NP. El viajante en su versión de decisión es NP-completo; en su versión de optimización, NP-difícil.
Qué hacer cuando el problema es NP-completo
Que un problema sea NP-completo no cierra la puerta, cambia la estrategia. Deja de tener sentido buscar el algoritmo exacto y eficiente, y empiezan a tener sentido cuatro caminos: aproximaciones con garantía, heurísticas sin garantía pero buenas en la práctica, algoritmos exactos exponenciales aceptables para instancias chicas, o explotar estructura del caso particular.
Los resolvedores de SAT modernos manejan instancias industriales con millones de variables. El peor caso sigue siendo exponencial; las instancias reales casi nunca son el peor caso.
Qué hacer cuando el problema es NP-completo
| Salida | Qué se resigna | Cuándo conviene |
|---|---|---|
| Aproximación con cota | el óptimo, dentro de un factor demostrado | hace falta una garantía |
| Heurística | cualquier garantía | las instancias reales son fáciles y se puede medir |
| Resolvedor general (SAT, ILP) | la previsibilidad del tiempo | el problema se puede expresar y las instancias no son las peores |
| Restringir el problema | generalidad | el caso real tiene estructura: el grafo es un árbol, los números son chicos |
| Aceptar el exponencial | nada | n es chico de verdad y no va a crecer |
Más a fondo · formalLo que P contra NP no dice
Tres precisiones que se pierden en las divulgaciones.
La primera: NP no significa «no polinomial». Significa no determinista polinomial, o sea que una solución propuesta se puede verificar en tiempo polinomial. P está contenido en NP: todo lo que se resuelve rápido también se verifica rápido.
La segunda: si P fuera igual a NP, no todo se volvería instantáneo. Un algoritmo es polinomial e inútil. La equivalencia sería un terremoto teórico, y las consecuencias prácticas dependerían de las constantes y los exponentes.
La tercera, la más interesante: si P fuera igual a NP, se caería la criptografía de clave pública, porque toda su seguridad se apoya en que factorizar y el logaritmo discreto sean difíciles. Y de paso, encontrar demostraciones matemáticas cortas se volvería mecánico, lo que para muchos es el argumento más fuerte de que P y NP no son iguales: sería demasiado bueno.
Cierre
P es resolver rápido, NP es verificar rápido, NP-completo es el núcleo duro de NP donde uno resuelto los resuelve a todos. Saber que un problema es NP-completo es información útil: dice que hay que dejar de buscar el algoritmo exacto y elegir qué se está dispuesto a resignar.
Autoevaluación
¿Lo entendiste?
Práctica