La classe di complessità P è spesso vista come un' astrazione matematica che modella quei task computazionali che ammettono un algoritmo efficiente. Questa ipotesi è chiamata tesi di Cobham-Edmonds. La classe di complessità NP, invece, contiene molti problemi che la gente vorrebbe risolvere in modo efficiente, ma per i quali non è noto alcun algoritmo efficiente, come il problema della soddisfazione booleana, il problema del sentiero Hamiltonian e il problema della copertura dei vertici. Dal momento che le macchine deterministiche di Turing sono speciali macchine di Turing non deterministiche, si osserva facilmente che ogni problema in P appartiene anche alla classe NP.
Quale classe di complessità è caratterizzata da task computazionali e algoritmi efficienti?
P P P