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


Segnala un errore o invia un suggerimento per migliorare la pagina



FacebookTwitterLinkedinLinkedin