回路計算量

入力が n ビットの論理回路は有向非巡回グラフであり、各ノード（回路計算量の場合、「ゲート」と呼ぶ）は、入次数 0 の入力ノード（n個の入力ビットのいずれかに対応）か、ANDゲート、ORゲート、NOTゲートである。これらのゲートのいずれかが出力ゲートとなる。このような回路が n 個の入力の関数を計算する。回路の大きさは、全ゲート数と、入力ゲートから出力ゲートまでの最大の長さ（すなわち、回路の深さ）で表される。

ブール関数 f の回路計算量（大きさと深さ）は、f を計算する回路のうちで最も小さい回路（あるいは浅い回路）の大きさ（や深さ）で表される。回路計算量の目標は、ブール関数群の最小の大きさや深さを決定することである。n ビット入力の関数 ${\displaystyle f_{n}}$ の回路計算量を求める場合、${\displaystyle f_{1},f_{2},...}$ といった小さい関数から始めて、漸近的に求める手法がよく使われる。

論理回路に関する複雑性クラスとして、AC⁰、AC、TC⁰、NCがある。

論理回路は一様でない計算模型の典型例であり、入力長が違えば回路も異なる。一方チューリングマシンのような一様な計算模型では、同じ計算機械を任意の入力長に使うことができる。従って、ある計算問題に対応した論理回路は（入力長に従って） ${\displaystyle C_{1},C_{2},...}$ のように複数存在し、${\displaystyle C_{n}}$ の回路は n ビットの入力を扱う。従って一様性はそれら論理回路群全体で成り立つものであり、個々の回路は計算資源を制限したチューリングマシンで計算可能である。

Vollmer の 1999年の著書（参考文献参照）によれば、回路計算量の研究に大きな影響を与えたものとして、Savage の1976年の著書^{[要文献特定詳細情報]}が挙げられる。

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