NP-difficile: differenze tra le versioni

Versione delle 10:50, 24 set 2014

Versione attuale delle 14:37, 21 set 2024

(20 versioni intermedie di 15 utenti non mostrate)

Riga 1:

{{NN|informatica|ottobre 2010}}

[[File:P_np_np-complete_np-hard.svg|thumb|upright=1.4|[[Diagramma di Eulero-Venn]] per le classi di complessità [[P_P (complessità)|P]], [[NP_NP (complessità)|NP]], [[NP-Completo]] e NP-hard]]

In [[Teoria della complessità computazionale|teoria della complessità]], i problemi '''NP-difficili''' o '''NP-ardui''' (in [[lingua inglese{{Inglese|inglese]] '''NP-hard'''}}, da ''nondetermistic polynomial-time hard problem'', "problema difficile nondeterministiconon 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 <math>H</math> è NP-difficile [[se e solo se]] esiste unogni problema [[NP-completo (complessità)|NP]] <math>L</math> che è [[riduzione in tempo polinomiale|polinomialmente riducibile]] ad <math>H</math>, ovvero tale che <math>L \leq_T H \;\; \forall L \in \text{NP} </math>. In altre parole, <math>L</math> deve poter essere risolto in tempo polinomiale da una [[macchina di Turing]] dotata di un [[macchina a oracolo|oracolo]] per <math>H</math>.<ref>Ovvero dotata di un meccanismo ipotetico che le consente di avere istantaneamente la soluzione del problema <math>H</math>. Se avendo la soluzione di <math>H</math> "gratis" la soluzione di <math>L</math> risulta "poco costosa" (vedi la definizione di [[classi di complessità P e NP|tempo polinomiale]]), se ne ricava che <math>H</math> non può essere significativamente più semplice di <math>L</math>.</ref> Da questa definizione si ricava che i problemi NP-difficili sono non meno difficili dei problemi [[NP-completo|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 [[problema di decisione|problemi di decisione]]; vi appartengono infatti anche problemi di [[ottimizzazione (matematica)|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 [[computer|calcolo]] è equivalente a un problema notoriamente NP-difficile significa dimostrare che è praticamente impossibile<ref>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 conseguenzeconseguenza, 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.</ref> 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 <math>H</math>, 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 <math>P=NP</math>. Sebbene non sia ancora stata trovata una dimostrazione, la comunità scientifica ritiene in generale che P ed NP non coincidano.<ref>La domanda "P=NP?" appartiene ai cosiddetti [[problemi per il millennio|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 GodelGödel]].</ref>

* Più precisamente: se <math>P \neq NP</math>, allora i problemi NP-difficili non hanno soluzione polinomiale. Viceversa, se fosse vero che <math>P = NP</math>, 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 (complessità)|NP]], allora H è anche [[NP-completo]] perché in tal caso la riduzione polinomiale rispetta i criteri di una riduzione tra problemi NP-completi.

== Esempi ==

[[File:Salesman.PNG|thumb|Un tipico problema NP-hard, il calcolo del minimo cammino completo in un grafo]]

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|cammino minimoHamiltoniano]] che unisce due punti su un [[grafo pesato]].

Ci sono [[Problema decisionale|problemi decisionali]] che sono NP-difficili ma non NP-completi, e ain questa categoriaclasse appartienerientrano ili celebreproblemi [[problemache dellasono fermatain [[EXPTIME]]:, datocioè untutti programmaquei (oproblemi decisionali risolvibili da una [[macchina deterministica di Turing]] nel tempo O(<math>2^{f(n)}</math>), edove l'insiemef(n) deiè datiuna chefunzione glipolinomiale. verrannoUn fornitiproblema è NP-hard se tutti i problemi in ingresso,NP stabiliresono seriducibili polinomialmente ad esso. Un esempio di problema NP-hard è il programmaproblema termineràdelle formule booleane soddisfacibili [[Soddisfacibilità booleana|SAT]]). Si può dimostrare che i problemi NP-completi sono polinomialmente riducibili a questo problema (una dimostrazione è nota per esempio per [[Soddisfacibilità booleana|3sat]]), ma il problema è anche notoriamente non decidibile e quindi non completo. 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 ==

Riga 23:

== 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.

Riga 29:

* '''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);

==Bibliografia==

{{Cita libro|autore = Michael R. Garey e David S. Johnson | anno = 1979 | titolo = [http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455 Computers and Intractability: A Guide to the Theory of NP-Completeness] | editore = W.H. Freeman | isbn = 0-7167-1045-5 }}

==Note==

<references />

==Bibliografia==

*{{Cita libro|autore = Michael R. Garey e David S. Johnson | anno = 1979 | titolo = [httphttps://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455 Computers and Intractability: A Guide to the Theory of NP-Completeness] | editore = W.H. Freeman | isbn = 0-7167-1045-5 }}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{FOLDOC|NP-hard|NP-hard}}

{{Classi di complessità}}

Line 40 ⟶ 44:

{{Portale|Informatica|Matematica}}

[[Categoria:ComplessitàClassi computazionaledi complessità]]

[[Categoria:Matematica per l'informatica]]