回路計算量

回路計算量（テンプレート:Lang-en-short）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。

概要

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

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

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

一様性

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

歴史

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

主な成果

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

複雑性クラス

回路計算量の複雑性クラスの多くはクラス群の階層で定義されている。任意の整数 i について、NCⁱというクラスが存在し、深さ $O({\log }^i(n))$ で入力端子数の制限された AND/OR/NOTゲートを使った多項式サイズの回路が属している。これらのクラスを総称して NC クラスと呼ぶ。入力端子数が無制限のゲートに関しては、ACⁱ とその総称としての AC クラスがある。ゲート数や深さが同じでも、使用するゲートが異なれば、回路計算量の複雑性クラスも異なる。

参考文献

• テンプレート:Cite book2
• Lecture notes for a course of Uri Zwick on circuit complexity
• Circuit Complexity before the Dawn of the New Millenium, a 1997 survey of the field by Eric Allender