NP Completezza

La NP Completezza è un argomento dell'analisi della complessità dei problemi. E' utilizzato per indicare i problemi di classe di complessità NP particolarmente estremi e difficili, per i quali non esiste alcuna possibilità d'essere convertiti in problemi di classe di complessità P anche in presenza di una infinita capacità computazionale. Nella Teoria della Complessità i problemi NP-Completi sono problemi non deterministici a tempo polinomiale per i quali non è possibile trovare un algoritmo in grado di risolvere il problema in un tempo polinomiale accettabile. I problemi NP-Completi sono un sottoinsieme dei problemi di classe NP. La classe dei problemi NP-Completi è anche indicata con l'abbreviazione NP-C.