Classi di complessità P e NP
Classi di complessità P e NP
Da Wikipedia, l'enciclopedia libera.
 | Questa voce o sezione di matematica non cita alcuna fonte o le fonti presenti sono insufficienti. Puoi migliorare questa voceaggiungendo citazioni dafonti attendibili seguendo le linee guida sull'uso delle fonti. |
La teoria della complessità computazionale è quella parte della teoria della computazione che studia la quantità di risorse richieste durante una computazione standard per risolvere un dato problema. Le risorse più comunemente studiate sono il tempo (quanti passi sono necessari a risolvere un problema) e lo spazio (quanta memoria è necessaria per risolvere un problema).
In questa teoria, la classe P consiste di tutti quei problemi di decisione che possono essere risolti con una macchina sequenziale deterministica in un tempo che è polinomiale rispetto alla dimensione dei dati di ingresso; la classe NP consiste di tutti quei problemi di decisione le cui soluzioni positive possono essere verificate in tempo polinomiale avendo le giuste informazioni, o equivalentemente, la cui soluzione può essere trovata in tempo polinomiale con una macchina non deterministica. Senza dubbio, il più importante problema aperto dell'informatica teorica riguarda la relazione tra queste due classi:
- P è uguale a NP?
La maggior parte degli esperti ritiene che la risposta sia probabilmente "no"; qualcuno crede che la domanda possa essere indecidibile rispetto agli assiomi correntemente accettati. Il grande logico Kurt Gödel, invece, in una lettera a John von Neumann, riteneva plausibile l'ipotesi P=NP. Un premio di un milione di dollari è stato offerto per la soluzione corretta (si tratta di uno dei problemi del millennio).
Un ruolo importante in questa discussione è giocato dall'insieme dei problemi NP-completi, che possono essere intuitivamente descritti come quei problemi in NP che meno probabilmente appartengono anche a P. (Vedere NP-completo per la definizione esatta.) Gli informatici teorici hanno dimostrato che se P è diverso da NP, allora nessun problema NP-completo appartiene a P.
Essenzialmente, la domanda P = NP si può riformulare così: se le soluzioni positive a problemi di tipo SÌ/NO possono essere verificate velocemente, ne segue che le risposte possono essere anche calcolate velocemente? Un esempio per avere un'idea di cosa ciò vuole dire. Dati due numeri grandi X e Y, potremmo chiederci se Y sia multiplo di un intero tra 1 e X, estremi esclusi. Per esempio potremmo chiederci se 69799 sia multiplo di un qualche intero tra 1 e 250. La risposta è SÌ, sebbene sia necessaria una discreta quantità di lavoro per scoprirlo a mano. D'altra parte, se qualcuno ci dicesse che la risposta è "SÌ, perché 223 è un divisore di 69799", allora potremo velocemente verificare questo fatto con un'unica divisione. Verificare che un numero è un divisore di un altro è molto più semplice che trovare il divisore stesso partendo da zero. L'informazione necessaria a verificare una risposta positiva è anche chiamata certificato. Concludiamo così che dati i certificati giusti, le risposte positive ai nostri problemi possono essere verificate velocemente (cioè in tempo polinomiale) e questo è il motivo per cui il problema è in NP. Non è noto se questo problema è in P. Il caso particolare in cui X=Y è stato dimostrato essere in P nel 2002.
Voci correlate
Collegamenti esterni
| Classi di complessità (elenco) |
|---|
| P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH |
0 commenti: