In teoria della complessità, i problemi NP-difficili o NP-ardui (, 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 è NP-difficile se e solo se ogni problema NP è polinomialmente riducibile ad , ovvero tale che . In altre parole, deve poter essere risolto in tempo polinomiale da una macchina di Turing dotata di un oracolo per .Ovvero dotata di un meccanismo ipotetico che le consente di avere istantaneamente la soluzione del problema . Se avendo la soluzione di "gratis" la soluzione di risulta "poco costosa" (vedi la definizione di tempo polinomiale), se ne ricava che non può essere significativamente più semplice di . 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 impossibileUno 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. 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à.

Osservazioni Dato che i problemi NP-completi sono riducibili l'uno all'altro in tempo polinomiale, e tutti i problemi in NP sono riducibili in tempo polinomiale a problemi NP-completi, si ricava che dato un qualunque problema NP-difficile , tutti i problemi in NP sono riducibili in tempo polinomiale a esso. Di conseguenza, se si trovasse una soluzione in tempo polinomiale a un qualunque problema NP-difficile, questa potrebbe essere utilizzata per risolvere tutti i problemi in NP. Questo dimostrerebbe che . Sebbene non sia ancora stata trovata una dimostrazione, la comunità scientifica ritiene in generale che P ed NP non coincidano.La domanda "P=NP?" appartiene ai cosiddetti problemi del millennio. Sebbene la tendenza generale della comunità scientifica è a ritenere che la risposta sia "no", l'ipotesi contraria è stata formulata anche da matematici illustri come Kurt Gödel. Più precisamente: se , allora i problemi NP-difficili non hanno soluzione polinomiale. Viceversa, se fosse vero che , da questo non si dedurrebbe la risolubilità polinomiale dei problemi NP-difficili. Se un problema di ottimizzazione H ha una versione L, dove L è NP-completo, allora H è NP-difficile; Se H appartiene ad NP, allora H è anche NP-completo perché in tal caso la riduzione polinomiale rispetta i criteri di una riduzione tra problemi NP-completi.

Esempi

Un esempio di problema NP-difficile è il problema di decisione noto come problema delle somme parziali o "SUBSET-SUM", e che corrisponde alla domanda: dato un insieme di interi, c'è almeno un suo sottoinsieme che ha come somma algebrica zero? Un celebre problema di ottimizzazione NP-difficile, che ha anche una fortissima valenza pratica, è quello di trovare il cammino hamiltoniano che unisce due punti su un grafo.

Ci sono problemi decisionali che sono NP-difficili ma non NP-completi, in questa classe rientrano i problemi che sono in EXPTIME, cioè tutti quei problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(), dove f(n) è una funzione polinomiale. Un problema è NP-hard se tutti i problemi in NP sono riducibili polinomialmente ad esso. Un esempio di problema NP-hard è il problema delle formule booleane soddisfacibili SAT). Si può dimostrare che i problemi NP-completi sono polinomialmente riducibili a questo problema (una dimostrazione è nota per esempio per 3sat). Ci sono tuttavia anche esempi di problemi che sono NP-difficili, decidibili, ma non NP-completi; un esempio è il problema del riconoscimento del linguaggio TQBF (True Quantified Boolean Formulas).

Definizione alternativa Una definizione alternativa di NP-hard che è spesso usata restringe NP-Hard a problemi decisionali e quindi usa la riduzione polinomiale al posto della riduzione di Turing. Così, formalmente un linguaggio L è NP-hard se .

Convenzioni sulla nomenclatura della famiglia NP La nomenclatura dei problemi NP è confusa: i problemi NP-ardui non sono in NP, nonostante vengano etichettati con tale nome. Nonostante questa contraddizione verbale, tale nome è ormai di uso comune. D'altro canto, il sistema di nomenclatura NP- ha un senso più profondo, che fa interesse alla sua classe di complessità generica, denominata anch'essa NP.

NP-completo - identifica problemi che sono completi dentro NP. NP-difficile - identifica problemi che sono almeno complessi quanto quelli in NP (ma non appartengono necessariamente ad NP); NP-semplici - identifica problemi che sono al massimo complessi quanto quelli in NP (ma non appartengono necessariamente ad NP); NP-equivalenti - identifica problemi che sono esattamente equivalenti ad NP, (ma non appartengono necessariamente ad NP);

Note

Bibliografia

Collegamenti esterni

Categoria:Classi di complessità