Classe di complessità: differenze tra le versioni

Versione delle 17:45, 28 dic 2008

Versione delle 14:55, 2 gen 2009

Riga 3:

:l'insieme di problemi che, se esiste la soluzione, possono essere risolti da una [[macchina astratta]] M usando <math>O(f(n))</math> della risorsa R, con <math>n</math> dimensione dell'input

Ad esempio, la classe [[NP (complessità)|'''NP''']] è l'insieme dei problemi di decisione che possono essere risolti da una [[macchina di Turing#Macchina di Turing non deterministica|macchina di Turing non deterministica]] in tempo polinomiale, mentre la classe [[P (complessità)|'''P''']] è l'insieme dei problemi di decisione che possono essere risolti da una [[macchina di Turing]] deterministica in spaziotempo polinomiale. Alcune classi di complessità sono insiemi di problemi costruttivi (cioè che richiedono di calcolare una funzione, e non di rispondere SÌ o NO), come ad esempio [[FP (complessità)|'''FP''']].

Molte classi di complessità possono essere caratterizzate in termini della [[logica matematica]] necessaria ad esprimerle; vedi [[complessità descrittiva]].