NP-difficile: differenze tra le versioni

Versione delle 15:41, 8 giu 2019

Versione attuale delle 14:37, 21 set 2024

(8 versioni intermedie di 7 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 (complessità)|P]], [[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 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 <math>H</math> è NP-difficile [[se e solo se]] ogni problema [[NP-completo (complessità)|NP]] <math>L</math> è [[riduzione in tempo polinomiale|polinomialmente riducibile]] ad <math>H</math>, ovvero tale che <math>L \leq_T H \;\; \forall L \in \text{NP-completo} </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.

Riga 15:

== 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 Hamiltoniano]] che unisce due punti su un [[grafo]].

Ci sono [[Problema decisionale|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(<math>2^{f(n)}</math>), 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 [[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]]). 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 34:

==Bibliografia==

*{{Cita libro|autore = Michael R. Garey e David S. Johnson | anno = 1979 | titolo = [https://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à}}