回路計算量
ブール関数 PARITY は、入力ビット群の 1 の数が奇数の場合に 1 を返すものだが、 A C 0 {\displaystyle AC^{0}} には含まれない。Ajtai(1983年)と Furst、Saxe、Sipser(1984年)がそれぞれ独立に発見した。Hasted(1987年)はさらに A C 0 {\displaystyle AC^{0}} に属して PARITY を計算する回路は指数関数的な大きさになることを示した。Smolensky(1986年)は、入力ビット数を数えて、それを任意の素数で割った余りを出力する回路で同じことが言えることを証明した。
単調関数 CLIQUE は多項式サイズの単調回路(否定を使わない、AND と OR だけの回路)では計算できない。Alexander Razborov(1985年)が最初に発見し、Alon と Boppana(1987年)がさらに発展させた。Raz と McKenzie(1999年)は、単調NC階層は無限であることを示した。
除算はTC0に含まれる(Hesse 2001年)。