NP-hard

En teoría de la complejidad computacional, la clase de complejidad NP-hard (o NP-complejo, o NP-difícil) es el conjunto de los problemas de decisión que contiene los problemas H tales que todo problema L en NP puede ser transformado polinomialmente en H. Esta clase puede ser descrita como aquella que contiene a los problemas de decisión que son como mínimo tan difíciles como un problema de NP. Esta afirmación se justifica porque si podemos encontrar un algoritmo A que resuelve uno de los problemas H de NP-hard en tiempo polinómico, entonces es posible construir un algoritmo que trabaje en tiempo polinómico para cualquier problema de NP ejecutando primero la reducción de este problema en H y luego ejecutando el algoritmo A. Asumiendo que el lenguaje L es NP-completo, 1. L está en NP 2. ∀L' en NP, L' ≤ L En el conjunto NP-Hard se asume que el lenguaje L satisface la propiedad 2, pero no la propiedad 1. La clase NP-completo puede definirse alternativamente como la intersección entre NP y NP-hard. Algunas consecuencias de la definición son: Como NP-completo es el tipo más costoso de la clase NP, el problema H es al menos tan costoso como NP, pero H no tiene por qué estar en NP y por tanto no tiene por qué ser un problema de decisión. Los problemas NP-completos se pueden transformar unos en otros por una reducción polinómica, los problemas NP-completos pueden ser resueltos en tiempo polinómico por reducción a H, así que todos los problemas de NP se reducen a H; sin embargo, esto implica utilizar dos tipos diferentes de transformaciones: de problemas de decisión NP-completos a un problema NP-completo L por transformaciones polinómicas, y de L a H por reducción polinómica de Turing. Si hay algún algoritmo polinómico para resolver un problema NP-hard, entonces...