Predefinição:Classes de complexidade vdeClasse de complexidades (Lista)Considerado viável DLOGTIME AC0 ACC0 TC0 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