NP-difficile

In teoria della complessità, i problemi NP-difficili o NP-ardui (in inglese NP-hard, da nondetermistic polynomial-time hard problem, "problema difficile non deterministico in tempo polinomiale") sono una classe di problemi che può essere definita informalmente come la classe dei problemi almeno difficili come i più difficili problemi delle classi di complessità P e NP. Più formalmente, un problema $H$ è NP-difficile se e solo se ogni problema NP $L$ è polinomialmente riducibile ad $H$ , ovvero tale che $L\leq _{T}H\;\;\forall L\in {\text{NP}}$ . In altre parole, $L$ deve poter essere risolto in tempo polinomiale da una macchina di Turing dotata di un oracolo per $H$ .^[1] Da questa definizione si ricava che i problemi NP-difficili sono non meno difficili dei problemi NP-completi, che a loro volta sono per definizione i più difficili delle classi P/NP.

La categoria dei problemi NP-difficili, a differenza delle classi P, NP e degli NP-completi, non è limitata per definizione ai soli problemi di decisione; vi appartengono infatti anche problemi di ottimizzazione e di altri generi.

La classe dei problemi NP-difficili ha una grande rilevanza sia teorica che pratica. In pratica, dimostrare che un problema di calcolo è equivalente a un problema notoriamente NP-difficile significa dimostrare che è praticamente impossibile^[2] trovare un modo efficiente di risolverlo, cosa che ha molte implicazioni in informatica. Da un punto di vista teorico, lo studio dei problemi NP-difficili è un elemento essenziale della ricerca su alcuni dei principali problemi aperti della complessità.

^ Ovvero dotata di un meccanismo ipotetico che le consente di avere istantaneamente la soluzione del problema $H$ . Se avendo la soluzione di $H$ "gratis" la soluzione di $L$ risulta "poco costosa" (vedi la definizione di tempo polinomiale), se ne ricava che $H$ non può essere significativamente più semplice di $L$ .
^ Uno dei problemi aperti della teoria della complessità è se sia possibile trovare un algoritmo efficiente (formalmente: in tempo polinomiale) per i problemi NP-completi. Di conseguenza, non è teoricamente impossibile che un algoritmo efficiente possa essere trovato per risolvere un problema NP-difficile. Tuttavia, nessun algoritmo del genere è mai stato identificato dalla comunità scientifica, e in generale (pur in assenza di una dimostrazione matematica) si propende per ritenere che un risultato del genere sia impossibile.

[1] Ovvero dotata di un meccanismo ipotetico che le consente di avere istantaneamente la soluzione del problema $H$ . Se avendo la soluzione di $H$ "gratis" la soluzione di $L$ risulta "poco costosa" (vedi la definizione di tempo polinomiale), se ne ricava che $H$ non può essere significativamente più semplice di $L$ .

[2] Uno dei problemi aperti della teoria della complessità è se sia possibile trovare un algoritmo efficiente (formalmente: in tempo polinomiale) per i problemi NP-completi. Di conseguenza, non è teoricamente impossibile che un algoritmo efficiente possa essere trovato per risolvere un problema NP-difficile. Tuttavia, nessun algoritmo del genere è mai stato identificato dalla comunità scientifica, e in generale (pur in assenza di una dimostrazione matematica) si propende per ritenere che un risultato del genere sia impossibile.

[1]

[2]