回路計算量
Vollmer の 1999年の著書(参考文献参照)によれば、回路計算量の研究に大きな影響を与えたものとして、Savage の1976年の著書が挙げられる。
回路計算量の複雑性クラスの多くはクラス群の階層で定義されている。任意の整数 i について、NCというクラスが存在し、深さ O ( log i  ( n ) ) {\displaystyle O(\log ^{i}(n))} で入力端子数の制限された AND/OR/NOTゲートを使った多項式サイズの回路が属している。これらのクラスを総称して NC クラスと呼ぶ。入力端子数が無制限のゲートに関しては、AC とその総称としての AC クラスがある。ゲート数や深さが同じでも、使用するゲートが異なれば、回路計算量の複雑性クラスも異なる。