Outras classes de complexidade importantes incluem BPP, ZPP e RP, que são definidas usando máquinas de Turing probabilística; AC e NC, que são definidas usando circuitos booleanos e BQP e QMA, que são definidas usando máquinas de Turing quânticas. #P é uma importante classe complexidade de problemas de contagem (que não são problemas de decisão). Classes como IP e AM são definidas usando sistemas de prova interativa. ALL é a classe de todos os problemas de decisão.