Le risorse del calcolo

Classi di complessità

CalcolabilitàEsponenzialeSpazio pol.Gerarchia polinomialeTempo pol.Spazio logaritmico⊊NEXP ⊊ R: inclusione stretta ricavata dai risultati del corso⊊R ⊊ RE: inclusione stretta dimostrata⊊R ⊊ coRE: inclusione stretta dimostrata≠RE ≠ coRE (ricavata dalla validità del primo ordine)L ⊊ PSPACEL ⊊ PSPACE: separazione dimostrataNL ⊊ PSPACENL ⊊ PSPACE: separazione dimostrataNP ⊊ NEXPNP ⊊ NEXP: separazione dimostrataP ⊊ EXPP ⊊ EXP: separazione dimostrataLspazio log nNL= coNLP= Σ₀ᴾ = Δ₁ᴾNP ∩ coNPprove corte in entrambi i versiNP= Σ₁ᴾcoNP= Π₁ᴾDPNP ∧ coNPΔ2P= P^NPΣ2P= NP^NPΠ2P= coNP^NPΣiPpiani i ≥ 3ΠiPpiani i ≥ 3PH⋃ ΣᵢᴾPSPACE= NPSPACEEXPtempo 2^polyNEXPnondet. 2^polyRdecidibiliREsemidecidibilicoREcomplementi di RE
inclusione dimostrata, non si sa se stretta
inclusione stretta dimostrata
separazione dimostrata tra classi lontane
non si sa nemmeno se una contiene l'altra