Problemas NP-duros: definición, ejemplos y diferencias con NP y NP-completo

Descubre qué son los problemas NP-duros: definición clara, ejemplos clave (TSP, parada) y cómo difieren de NP y NP-completo. Guía esencial para estudiantes e investigadores.

Un problema NP-duro es, en términos informales, un problema cuyo nivel de dificultad es al menos tan grande como el del problema más difícil de la clase NP: resolver cualquier problema de NP puede reducirse a resolver un problema NP‑duro. Más formalmente, bajo la reducción usual en tiempo polinómico (reducción many‑one o reducción de Karp), un lenguaje L es NP‑duro si para todo lenguaje L' en NP existe una función computable en tiempo polinómico f tal que x pertenece a L' si y sólo si f(x) pertenece a L. Los problemas NP‑duros pueden o no pertenecer a NP. Cuando un problema es NP‑duro y además está en NP (es decir, sus soluciones se pueden verificar en tiempo polinómico), se dice que es NP‑completo.

Definición y matices

• NP: clase de problemas de decisión cuyas respuestas "sí" pueden ser verificadas en tiempo polinómico dadas pruebas (certificados) apropiadas.
• NP‑duro: problema H tal que todo problema en NP puede reducirse en tiempo polinómico a H. No exige que H esté en NP ni que sea decidible.
• NP‑completo: problemas que son a la vez NP y NP‑duros; son los "más difíciles" dentro de NP.
• Existen distintos tipos de reducciones (reducciones en tiempo polinómico "many‑one" de Karp, o reducciones con oráculo/Turing de Cook). La elección de la reducción afecta qué problemas se consideran NP‑duros bajo esa noción concreta.

Ejemplos ilustrativos

Ejemplo que es NP‑duro y además está en NP (por tanto NP‑completo, en su versión de decisión):

Un vendedor ambulante quiere visitar 100 ciudades en coche, empezando y terminando su viaje en casa. Tiene un suministro limitado de gasolina, por lo que sólo puede conducir un total de 10.000 kilómetros. Quiere saber si puede visitar todas las ciudades sin quedarse sin gasolina.

La gente no sabe cómo resolver este problema más rápido que probando todas las posibles rutas (explorar exponencialmente muchas permutaciones), pero si se encuentra una solución que permita al vendedor hacer esto, podemos utilizar un algoritmo para comprobar que es cierto. Este problema también se conoce como problema del vendedor ambulante.

Nota: la versión de decisión del problema del vendedor ambulante (¿existe un tour cuya longitud total sea ≤ B?) es NP‑completa; la versión de optimización (encontrar la ruta más corta) se suele llamar NP‑duro porque es una tarea de optimización, no puramente de decisión.

Ejemplo que es NP‑duro pero no está en NP (ejemplo de problema indecidible):

Considere el siguiente programa:

while(true){ continúa; }

La pregunta "si alguien inicia un programa como este, ¿corre para siempre?" es una instancia del problema de la parada (Halting problem). El problema de la parada es indecidible: no existe un algoritmo que responda correctamente para todas las entradas. Además, se puede mostrar que el problema de la parada es al menos tan difícil como cualquier problema en NP (puede usarse para codificar la existencia de certificados), por lo que es NP‑duro. Sin embargo, no pertenece a NP (ni siquiera es decidible), de modo que es un ejemplo típico de problema NP‑duro que no está en NP.

Diferencias clave entre NP, NP‑duro y NP‑completo

• Pertenencia a NP: Un problema en NP tiene soluciones cuya validez se puede comprobar en tiempo polinómico. Un problema NP‑duro no necesita cumplir esto.
• Mayor dificultad: Ser NP‑duro significa que el problema es, en el sentido de reducciones polinómicas, al menos tan difícil como cualquier problema en NP. No implica que el problema sea decidible.
• NP‑completo: son los problemas dentro de NP que son los más difíciles de esa clase; si se encontrase un algoritmo polinómico para cualquier problema NP‑completo, entonces P = NP (es decir, todos los problemas de NP serían resolvibles en tiempo polinómico).
• Problemas de optimización vs decisión: Muchas veces se habla de NP‑dureza para problemas de optimización (por ejemplo, "encontrar la mejor solución"); la noción formal de NP y NP‑completo se define para problemas de decisión. Por eso se convierte una tarea de optimización en una pregunta de decisión (¿existe una solución con coste ≤ B?) para aplicar la teoría de NP‑completitud.

Implicaciones prácticas y observaciones

• Que un problema sea NP‑duro no significa que no existan algoritmos eficientes para casos prácticos o instancias concretas; sólo afirma que no se conoce (y es muy improbable) un algoritmo polinómico que funcione para todas las instancias, a menos que P = NP.
• Para muchos problemas NP‑duros se emplean algoritmos aproximados, heurísticos, o algoritmos exactos que funcionan bien en instancias pequeñas o con estructura especial.
• Existen problemas incluso más difíciles (indecidibles) que son NP‑duros bajo reducciones polinómicas, como el problema de la parada o el problema de correspondencia de Post.

En resumen: NP‑duro es una medida de dificultad relativa (vía reducciones) frente a toda la clase NP; NP exige verificabilidad en tiempo polinómico; NP‑completo combina ambas propiedades. Mantener clara la distinción entre problemas de decisión y de optimización, y entre distintos tipos de reducciones, ayuda a entender por qué algunos problemas NP‑duros no pertenecen a NP y por qué la NP‑completitud marca la frontera de lo que, hoy por hoy, consideramos intrínsecamente difícil pero verificable.

Preguntas y respuestas

P: ¿Qué es un problema NP-duro?

P: ¿Se puede comprobar rápidamente una solución verdadera para todos los problemas NP-duros?

P: ¿Cómo se denomina la categoría de los problemas NP-duros que también son problemas NP?

P: ¿Son todos los problemas NP-duros NP-completos?

P: ¿Son fáciles de resolver los problemas NP-duros?

P: ¿Tiene alguna ventaja resolver problemas NP-duros?

P: ¿Se está investigando en la resolución de problemas NP-duros?

Búsqueda por letra