Tag Archives: np problems

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.