AC0

AC ⁰は回路複雑度で使用される複雑度クラスです。これはAC階層の中で最小のクラスであり、深さO(1)および多項式サイズの回路のすべてのファミリで構成され、ファンインが無制限のANDゲートおよびORゲート（入力でのみNOTゲートを許可）が含まれます。[1] したがって、ファンインが制限されたANDゲートおよびORゲートのみを持つNC ^{0が含まれます。[ 1 ]}

整数の加算と減算はAC ⁰で計算可能ですが^[2]、乗算は計算できません（具体的には、入力が通常の2進数^[3]または整数の10進数表現の2つの整数である場合）。

AC ⁰は回路クラスなので、P/polyと同様に、あらゆる単項言語も含まれます。

記述的複雑さの観点から見ると、DLOGTIME -均一AC ^0は、 BIT述語を追加した一階述語論理で記述可能なすべての言語の記述クラスFO +BITに等しい。または、FO(+, ×)、あるいは対数階層のチューリングマシンで記述可能である。^[4]

1984年にFurst、Saxe、およびSipserは、入力ビットのパリティの計算は（前述の2つの入力を持つ加算/減算問題とは異なり）、非均一性があってもAC ^{0回路では決定できないことを示しました。 [5] [1]} したがって、AC ^{0 は}NC ¹と等しくありません。後者のクラスの回路の族はパリティを計算できるためです。^{[1]より正確な境界は}スイッチング補題 から得られます。それらを使用して、多項式階層とPSPACEの間には神託の分離があることが示されています。