Il problema P versus NP: classi di complessità.

Questo è l’unico problema del Millennio che abbia a che fare con i computer. “Si tratta di un interrogativo sull’efficienza con cui i computer possono risolvere problemi. Gli esperti di scienze informatiche suddividono i compiti computazionali in due categorie principali: compiti di tipo P, che possono essere affrontati efficacemente da un computer, e compiti di tipo E la cui soluzione potrebbe richiedere milioni di anni. Purtroppo, la maggior parte dei grandi problemi computazionali che sorgono nell’industria e nel commercio ricade in una terza categoria, NP, che sembra essere intermedia fra N ed E. Ma lo è davvero? Non potrebbe essere solo una versione mascherata di P? Dopo trent’anni di tentativi, nessuno, finora, è stato in grado di dimostrare se P e NP siano, o no, la medesima cosa.

Il problema è interessante e intrigante, e per maggiori info vi rimando alla pagina di Wikipedia.

One thought on “Il problema P versus NP: classi di complessità.

  1. NDR (da Wikipedia): Un ruolo importante in questa discussione è giocato dall’insieme dei problemi 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.

Leave a Reply

Your email address will not be published. Required fields are marked *