NP (complessità)
insieme dei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale / Da Wikipedia, l'enciclopedia encyclopedia
La classe di problemi comprende tutti quei problemi decisionali che, per trovare una soluzione su una macchina di Turing non deterministica, impiegano un tempo polinomiale. La classe NP prende il suo nome dall'abbreviazione di Nondeterministic Polynomial Time.
La classe può essere definita in modo alternativo andando a sfruttare le macchine di Turing non deterministiche. Infatti si avrà che dato come un insieme di parole su un alfabeto , allora è nella classe se e solo se esiste una macchina di Turing non deterministica di complessità polinomiale che, per ogni input , ha almeno una computazione che converge.
In sostanza qualora esiste una macchina di Turing non deterministica che accetta (quindi converge per ogni input ).
Presa una macchina di Turing non deterministica di complessità polinomiale, allora essa accetterà un linguaggio il quale sarà un problema che appartiene alla classe . Tale macchina di Turing dunque, per ogni input avrà fra tutte le possibili computazioni su tale input, una che si arresta.
Invece se l'input che si fornisce alla macchina di Turing che accetta non appartiene a quest'ultimo linguaggio, allora si avranno solo computazioni infinite o computazioni massimali non accettanti.
Si ha che . Da tale affermazione si evince innanzitutto che tutti i problemi di classe P sono anche problemi di classe NP.
A seguito si mostra che la classe può essere caratterizzata come quella classe di problemi per i quali si è in grado di verificare in modo rapido se una possibile soluzione è effettivamente tale.