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.

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.