Predefinição:Classes de complexidade

Origem: Wikipédia, a enciclopédia livre.

v d e Classe de complexidades (Lista)
Considerado viável	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-completo ZPP RP BPP BQP APX
Suspeita inviável	UP NP NP-completo NP-hard co-NP co-NP-completo AM QMA PH ⊕P PP #P #P-completo IP PSPACE PSPACE-completude
Considerado inviável	EXPTIME NEXPTIME EXPSPACE ELEMENTAR PR R RE ALL
Hierarquias de classe	Hierarquia polinomial Hierarquia exponencial Hierarquia de Grzegorczyk Hierarquia aritmética Hierarquia Boolean
Famílias de classe	DTIME NTIME DSPACE NSPACE Provas verificáveis probabilisticamente Sistema de prova interativa