Classi di complessità P e NP: differenze tra le versioni

{{vedi anche|NP-completo}}

Un ruolo importante in questa discussione è giocato dall'insieme dei problemi [[NP-completo|NP-completi]], che possono essere intuitivamente descritti come quei problemi che ''sicuramente'' non apparterrebbero a '''P''' se '''P''' fosse diverso da '''NP'''. Al contrario, dimostrando anche per un solo problema [[NP-completo]] la sua appartenenza a '''P''', si otterrebbe una dimostrazione che '''P''' e '''NP''' sono equivalenti. In un certo senso, i problemi NP-completi sono quelli che meno probabilmente appartengono anche a '''P'''.

 

== Bibliografia ==

* [[P (complessità)]]

* [[NP (complessità)]]

 

== Collegamenti esterni ==