回路計算量

回路計算量（英: Circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。
概要.
入力が "n" ビットの論理回路は有向非環状グラフであり、各ノード（回路計算量の場合、「ゲート」と呼ぶ）は、入次数 0 の入力ノード（"n"個の入力ビットのいずれかに対応）か、ANDゲート、ORゲート、NOTゲートである。これらのゲートのいずれかが出力ゲートとなる。このような回路が "n" 個の入力の関数を計算する。回路の大きさは、全ゲート数と、入力ゲートから出力ゲートまでの最大の長さ（すなわち、回路の深さ）で表される。
ブール関数 "f" の回路計算量（大きさと深さ）は、"f" を計算する回路のうちで最も小さい回路（あるいは浅い回路）の大きさ（や深さ）で表される。回路計算量の目標は、ブール関数群の最小の大きさや深さを決定することである。"n" ビット入力の関数 formula_1 の回路計算量を求める場合、formula_2 といった小さい関数から始めて、漸近的に求める手法がよく使われる。
論理回路に関する複雑性クラスとして、AC0、AC、TC0、NCがある。
一様性.
論理回路は一様でない計算模型の典型例であり、入力長が違えば回路も異なる。一方チューリングマシンのような一様な計算模型では、同じ計算機械を任意の入力長に使うことができる。従って、ある計算問題に対応した論理回路は（入力長に従って） formula_3 のように複数存在し、formula_4 の回路は "n" ビットの入力を扱う。従って一様性はそれら論理回路群全体で成り立つものであり、個々の回路は計算資源を制限したチューリングマシンで計算可能である。
歴史.
Vollmer の 1999年の著書（参考文献参照）によれば、回路計算量の研究に大きな影響を与えたものとして、Savage の1976年の著書が挙げられる。
複雑性クラス.
回路計算量の複雑性クラスの多くはクラス群の階層で定義されている。任意の整数 "i" について、NCiというクラスが存在し、深さ formula_7 で入力端子数の制限された AND/OR/NOTゲートを使った多項式サイズの回路が属している。これらのクラスを総称して NC クラスと呼ぶ。入力端子数が無制限のゲートに関しては、ACi とその総称としての AC クラスがある。ゲート数や深さが同じでも、使用するゲートが異なれば、回路計算量の複雑性クラスも異なる。