NP-hard
Un problema NP-duro es un problema de sí/no en el que encontrar una solución para él es al menos tan difícil como encontrar una solución para el problema más difícil cuya solución se puede comprobar rápidamente como verdadera. Algunos problemas NP-duros son aquellos cuya solución se puede comprobar rápidamente (problemas NP) y otros no. Los problemas NP-duros que también son problemas NP entran en una categoría llamada NP-completo.
Un ejemplo de un problema que es al menos tan difícil de resolver como cualquier otro problema para el que podemos comprobar rápidamente las soluciones, que además es rápidamente comprobable (es tanto NP-duro como NP):
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 respuestas posibles, 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.
Un ejemplo de un problema que es al menos tan difícil de resolver como cualquier otro problema del que podemos comprobar rápidamente las soluciones, pero que no se puede comprobar rápidamente (es NP-duro, pero no es NP):
si alguien inicia un programa que simplemente va,
while(true){ continúa; }y nunca la detiene, ¿corre para siempre?
No se conoce la solución a todos los problemas de este tipo, y tampoco se puede comprobar.
Preguntas y respuestas
P: ¿Qué es un problema NP-duro?
R: Un problema NP-duro es un tipo de problema matemático utilizado en informática que es un problema sí/no en el que encontrar una solución para él es al menos tan difícil como encontrar una solución para el problema más difícil cuya solución pueda comprobarse rápidamente como verdadera.
P: ¿Se puede comprobar rápidamente una solución verdadera para todos los problemas NP-duros?
R: No, sólo algunos problemas NP-duros, llamados problemas NP, tienen soluciones que se pueden comprobar rápidamente.
P: ¿Cómo se denomina la categoría de los problemas NP-duros que también son problemas NP?
R: Los problemas NP-duros que también son problemas NP encajan en una categoría llamada NP-completos.
P: ¿Son todos los problemas NP-duros NP-completos?
R: No, no todos los problemas NP-duros son NP-completos. Sólo los que también son problemas NP entran en esta categoría.
P: ¿Son fáciles de resolver los problemas NP-duros?
R: No, los problemas NP-duros no son fáciles de resolver. De hecho, encontrar una solución para ellos es al menos tan difícil como encontrar una solución para el problema más difícil cuya solución pueda comprobarse rápidamente como verdadera.
P: ¿Tiene alguna ventaja resolver problemas NP-duros?
R: Sí, resolver problemas NP-duros puede proporcionar ventajas en diversos campos, como la informática, la física y las ciencias sociales, ya que pueden requerir cálculos y modelizaciones complejas.
P: ¿Se está investigando en la resolución de problemas NP-duros?
R: Sí, la investigación en la resolución de problemas NP-duros es continua, ya que estos problemas siguen siendo relevantes en diversos campos, y encontrar algoritmos y soluciones eficientes puede tener implicaciones significativas.
