classe di complessità

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 della risorsa R, con dimensione dell'input Ad esempio, la classe NP è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, mentre la classe P è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing deterministica in tempo 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 . Molte classi di complessità possono essere caratterizzate in termini della logica matematica necessaria ad esprimerle; vedi . Gli possono essere usati per definire classi di complessità senza riferirsi ad un concreto.