Altre classi di complessità importanti includono BPP, ZPP e RP, che sono definiti utilizzando macchine probabilistiche Turing; AC e NC, che sono definiti utilizzando circuiti booleani; e BQP e QMA, che sono definiti utilizzando macchine quantistiche Turing. #P è un' importante classe di complessità dei problemi di conteggio (non problemi decisionali). Classi come IP e AM sono definite utilizzando sistemi di prova interattiva. TUTTI sono la classe di tutti i problemi decisionali.
AC e NC sono classi di complessità tipicamente associate a quale tipo di circuito?
circuiti booleani;