OKPEDIA ANALISI COMPLESSITà

Classe di complessità NP

Nella classe di complessità NP sono compresi i problemi polinomiali non deterministici. Un problema di classe NP può essere risolto e verificato in tempi accettabili da un algoritmo in modo non deterministico. Sulla base delle "giuste" informazioni la macchina non deterministica individua una soluzione e la verifica in tempo polinomiale. Un esempio di problema di complessità NP è il computo di tutti i divisori dell'insieme dei numeri reali. In tali casi, non disponendo di un infinito numero di risorse informatiche, l'algoritmo non potrà verificare tutte le soluzioni del problema. Potrà elaborare in tempi accettabili soltanto una soluzione non deterministica.

CLASSE DI COMPLESSITA

La classe di complessità NP è una classe di complessità nell'ambito dell'analisi della complessità dei problemi. All'interno della classe di complessità NP sono compresi i problemi di classe di complessità P e i problemi di classe di complessità NP completi.

https://www.okpedia.it/classe_di_complessita_np




Questo sito utilizza cookie tecnici. Sono presenti alcuni cookie di terzi ( Gooogle, Facebook ) per la personalizzazione degli annunci pubblicitari. Cliccando su OK, scorrendo la pagina o proseguendo la navigazione in altra maniera acconsenti all’uso dei cookie.

Per ulteriori informazioni o per revocare il consenso fai riferimento alla Privacy del sito.