Classe di complessità: differenze tra le versioni

Versione delle 00:22, 29 lug 2006

Versione delle 11:37, 5 set 2006

Riga 1:

Nella [[teoria della complessità computazionale]], una '''classe di complessità''' è un insieme di problemi di una certa complessità. Un esempio tipico di definizione di classe di complessità ha la forma:

: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 [[PSPACE|'''PSPACE''']]] è l'insieme dei problemi di decisione che possono essere risolti da una [[macchina di Turing]] deterministica in spazio 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''']].