NP-hard

En teoria de la complexitat computacional, la classe de complexitat NP-hard (o NP-complex, o NP-difícil) és el conjunt dels problemes de decisió que conté els problemes H tals que tot problema L en NP pot ser transformat polinomialmente en H. Esta classe pot ser descrita com aquella que conté als problemes de decisió que són com a mínim tan difícils com un problema de NP. Esta afirmació es justifica perque si podem trobar un algoritme A que resol un dels problemes H de NP-hard en temps polinòmic, llavors és possible construir un algoritme que treballe en temps polinòmic per a qualsevol problema de NP eixecutant primer la reducció d'este problema en H i després eixecutant l'algoritme A.

Assumint que el llenguage L és NP-complet,

1. L està en NP

2. ∀L' en NP, L' ≤ L

En el conjunt NP-Hard s'assumix que el llenguage L satisfà la propietat 2, pero no la propietat 1.

La classe NP-complet pot definir-se alternativament com l'intersecció entre NP i NP-hard.

Algunes conseqüències de la definició són:

Com NP-complet és el tipo més costós de la classe NP, el problema H és a lo manco tan costós com NP, pero H no té per qué estar en NP i per tant no té per qué ser un problema de decisió.

Els problemes NP-complets es poden transformar uns en uns atres per una reducció polinòmica, els problemes NP-complets poden ser resolts en temps polinòmic per reducció a H, aixina que tots els problemes de NP es reduïxen a H; no obstant, açò implica utilisar dos tipos diferents de transformacions: de problemes de decisió NP-complets a un problema NP-complet L per transformacions polinòmiques, i de L a H per reducció polinòmica de Turing.

Si hi ha algun algoritme polinòmic per a resoldre un problema NP-hard, llavors hi ha algoritmes per a resoldre tots els problemes de NP en temps polinòmic, açò significaria que P=NP.

Si un problema d'optimisació H té una versió NP-completa, llavors H és NP-hard.

Si H pertany a NP, llavors H pertany també a NP-complet perque en este cas existix una transformació polinòmica de Turing que complix els requisits de les transformacions polinòmiques.

Un error comú és pensar que NP en NP-hard vol dir no polinòmic, ya que encara que hi ha séries sospites sobre que no existixen algoritmes per a resoldre estos problemes en temps polinòmic, açò mai ha segut demostrat.

Eixemples

El problema de la suma de subconjunts és un eixemple de problema NP-hard i es definix com seguix: donat un conjunt S de sancers, ¿existix un subconjunt no buit de S els elements de la qual sumixen zero?

Existixen problemes NP-hard que no són NP-complets, per eixemple el problema de parada. Este problema consistix en prendre un programa i les seues senyes i decidir si va a terminar o si s'eixecutarà indefinidament. Es tracta d'un problema de decisió i és fàcil demostrar que és NP-hard pero no NP-complet. Per eixemple, el problema de satisfacibilidad booleana pot reduir-se al problema de parada transformant-ho en la descripció d'una màquina de Turing que prova tots els valors de les variables; quan troba una combinació que satisfà la fòrmula es deté i en cas contrari reintenta des del principi, quedant-se en un llaç infinit. Per a vore que el problema de parada no està en NP és suficient notar que tots els problemes de NP tenen un algoritme associat pero el problema de la parada és indecidible.

Convenció de noms que inclouen les sigles NP

Els noms de famílies de problemes en les sigles NP és alguna cosa confusa. Els problemes NP-hard no són tots NP, a pesar de que estes sigles apareixen és el nom de la família. No obstant, els noms estan actualment molt arraïlats i plantejar un canvi de nomenclatura resulta poc realista. Per una atra part, les famílies de problemes en les sigles NP són totes definides prenent com a referència la família NP:

NP-complet — significa problemes que són complets en NP, és dir, els més difícils de resoldre en NP;

NP-hard — (NP-difícil) vol dir a lo manco tan complex com NP (pero no necessàriament en NP);

NP-easy — (NP-fàcil) vol dir com molt tan difícil com NP (pero no necessàriament en NP);

NP-equivalent — significa igualment difícil que NP, (pero no necessàriament en NP).

Vore també

Este artícul conté una traducció derivada de «NP-hard» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.