回路計算量のソースを表示

'''回路計算量'''（{{Lang-en-short|circuit complexity}}）とは、[[計算複雑性理論]]において、[[ブール関数]]をその計算に要する[[計算資源]]の量によって分類することを指す。回路計算量では、それらの資源量は[[論理回路]]の大きさや深さで表される。

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

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

論理回路に関する[[複雑性クラス]]として、[[AC0|'''AC<sup>0</sup>''']]、[[AC (計算複雑性理論)|'''AC''']]、[[TC0|'''TC<sup>0</sup>''']]、[[NC (計算複雑性理論)|'''NC''']]がある。

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

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

=== 主な成果 ===
* ブール関数 PARITY は、入力ビット群の 1 の数が奇数の場合に 1 を返すものだが、<math>AC^0</math> には含まれない。Ajtai（1983）<ref name="Ajtai_1983" /><ref name="Ajtai-Komlós-Szemerédi_1983" />と Furst、Saxe、Sipser（1984）<ref name="Furst-Saxe-Sipser_1984" />がそれぞれ独立に発見した。Hasted（1987）{{要文献特定詳細情報|date=2024年5月}}はさらに <math>AC^0</math> に属して PARITY を計算する回路は指数関数的な大きさになることを示した。Smolensky（1987）<ref name="Smolensky_1987" />は、入力ビット数を数えて、それを任意の素数で割った余りを出力する回路で同じことが言えることを証明した。
*単調関数 CLIQUE は多項式サイズの単調回路（否定を使わない、AND と OR だけの回路）では計算できない。Razborov（1985）<ref name="Razborov_1985" />が最初に発見し、Alon と Boppana（1987）<ref name="Alon-Boppana_1987" />がさらに発展させた。Raz と McKenzie（1999）<ref name="Raz-McKenzie_1999" />は、単調NC階層は無限であることを示した。
*除算は'''TC0'''に含まれる（Hesse 2001）<ref name="Hesse_2001" />。

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

== 脚注 ==
{{reflist|refs=
<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite book2
 | last1 = Ajtai | first1 = Miklós | author1-link = Miklós Ajtai
 | last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)
 | last3 = Szemerédi | first3 = Endre | author3-link = Endre Szemerédi
 | contribution = An <math>O(n\log n)</math> sorting network
 | doi = 10.1145/800061.808726
 | pages = 1–9
 | publisher = Association for Computing Machinery
 | title = Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA
 | year = 1983}}</ref>
<ref name="Ajtai_1983">{{cite journal2 |author-first=Miklós |author-last=Ajtai |author-link=Miklós Ajtai |title=<math>\Sigma^1_1</math>-formulae on finite structures |journal=Annals of Pure and Applied Logic |date=1983 |volume=24 |pages=1–24 |doi=10.1016/0168-0072(83)90038-6|doi-access= }}</ref>
<ref name="Furst-Saxe-Sipser_1984">{{cite journal2 |author-last1=Furst |author-first1=Merrick L. |author-last2=Saxe |author-first2=James Benjamin |author-link2=James Benjamin Saxe |author-last3=Sipser |author-first3=Michael Fredric |author-link3=Michael Fredric Sipser |doi=10.1007/BF01744431 |issue=1 |journal=[[Mathematical Systems Theory]] |mr=738749 |pages=13–27 |title=Parity, circuits, and the polynomial-time hierarchy |volume=17 |date=1984|s2cid=6306235 }}</ref>
<ref name="Hesse_2001">{{cite conference |author-first=William |author-last=Hesse |title=Division is in uniform TC<sup>0</sup> |date=2001 |pages=104–114 |book-title=Proceedings of the 28th International Colloquium on Automata, Languages and Programming |publisher=[[Springer Verlag]]}}</ref>
<ref name="Raz-McKenzie_1999">{{cite journal2 |author-first1=Ran |author-last1=Raz |author-link1=Ran Raz |author-first2=Pierre |author-last2=McKenzie |title=Separation of the monotone NC hierarchy |journal=[[Combinatorica]] |volume=19 |number=3 |date=1999 |pages=403–435 |doi=10.1007/s004930050062}}</ref>
<ref name="Razborov_1985">{{cite journal2 |author-first=Aleksandr Aleksandrovich |author-last=Razborov |author-link=Aleksandr Aleksandrovich Razborov |title=Lower bounds on the monotone complexity of some Boolean functions |date=1985 |journal=[[Soviet Mathematics - Doklady]] |issn=0197-6788 |volume=31 |pages=354–357}}</ref>
<ref name="Smolensky_1987">{{cite conference |author-first=Roman |author-last=Smolensky |title=Algebraic methods in the theory of lower bounds for Boolean circuit complexity |date=1987 |pages=77–82 |book-title=Proceedings of the 19th Annual ACM Symposium on Theory of Computing |publisher=[[Association for Computing Machinery]] |doi=10.1145/28395.28404|doi-access=free }}</ref>
<ref name="Alon-Boppana_1987">{{cite journal2 |author-first1=Noga |author-last1=Alon |author-link1=Noga Alon |author-first2=Ravi B. |author-last2=Boppana |title=The monotone circuit complexity of Boolean functions |journal=[[Combinatorica]] |volume=7 |date=1987 |number=1 |pages=1–22 |doi=10.1007/bf02579196 |citeseerx=10.1.1.300.9623|s2cid=17397273 }}</ref>
}}

== 参考文献 ==

*{{cite book2 |title=Introduction to Circuit Complexity: a Uniform Approach |last=Vollmer |first=Heribert |publisher=Springer Verlag |date=1999 |id=ISBN 3-540-64310-9}}
*[http://www.math.tau.ac.il/~zwick/scribe-boolean.html Lecture notes for a course of Uri Zwick on circuit complexity]
*[https://link.springer.com/chapter/10.1007/3-540-62034-6_33 ''Circuit Complexity before the Dawn of the New Millenium'', a 1997 survey of the field by Eric Allender]

{{DEFAULTSORT:かいろけいさんりよう}}
[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]