「回路計算量」の版間の差分
削除された内容 追加された内容
Vissel0126 (会話 | 投稿記録) 編集の要約なし |
Vissel0126 (会話 | 投稿記録) 編集の要約なし タグ: 2017年版ソースエディター |
||
| 23行目: | 23行目: | ||
== 脚注 == |
== 脚注 == |
||
{{reflist|refs= |
|||
{{reflist|refs=<ref name="Sipser_1997">{{cite book |author-last=Sipser |author-first=Michael |author-link=Michael Sipser |date=1997 |title=Introduction to the theory of computation |publication-place=Boston, USA |edition=1 |isbn= |publisher=PWS Publishing Company |page=324}}</ref> |
|||
<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite |
<ref name="Ajtai-Komlós-Szemerédi_1983">{{cite book2 |
||
| last1 = Ajtai | first1 = Miklós | author1-link = Miklós Ajtai |
| last1 = Ajtai | first1 = Miklós | author1-link = Miklós Ajtai |
||
| last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician) |
| last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician) |
||
| 34行目: | 34行目: | ||
| title = Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA |
| title = Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA |
||
| year = 1983}}</ref> |
| year = 1983}}</ref> |
||
<ref name="Ajtai_1983">{{cite |
<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 |
<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="Santhanam_2007">{{cite conference |author-last=Santhanam |author-first=Rahul |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.1811 |title=Circuit lower bounds for Merlin-Arthur classes |book-title=STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing |date=2007 |pages=275–283 |doi=10.1145/1250790.1250832 |citeseerx=10.1.1.92.4422}}</ref> |
|||
<ref name="Williams_2011">{{cite conference |author-last=Williams |author-first=Richard Ryan |author-link=Richard Ryan Williams |title=Non-Uniform ACC Circuit Lower Bounds |url=http://www.stanford.edu/~rrwill/acc-lbs.pdf |doi=10.1109/CCC.2011.36 |date=2011 |book-title=CCC 2011: Proceedings of the 26th Annual IEEE Conference on Computational Complexity |pages=115–125}}</ref> |
|||
<ref name="Kabanets-Impagliazzo_2004">{{cite journal |author-last1=Kabanets |author-first1=Valentine |author-last2=Impagliazzo |author-first2=Russell Graham |author-link3=Russell Graham Impagliazzo |journal=Computational Complexity |doi=10.1007/s00037-004-0182-6 |title=Derandomizing polynomial identity tests means proving circuit lower bounds |pages=1–46 |volume=13 |number=1 |date=2004|s2cid=12451799 }}</ref> |
|||
<ref name="Razborov-Rudich_1997">{{cite news |author-first1=Aleksandr Aleksandrovich |author-last1=Razborov |author-link1=Aleksandr Aleksandrovich Razborov |author-first2=Steven |author-last2=Rudich |author-link2=Steven Rudich |title=Natural proofs |journal=[[Journal of Computer and System Sciences]] |volume=55 |pages=24–35 |date=1997}}</ref> |
|||
<ref name="Carmosino-Impagliazzo-Kabanets-Kolokolova_2016">{{cite news |author-first1=Marco |author-last1=Carmosino |author-first2=Russell Graham |author-last2=Impagliazzo |author-link2=Russell Graham Impagliazzo |author-first3=Valentine |author-last3=Kabanets |author-first4=Antonina |author-last4=Kolokolova |title=Learning algorithms from natural proofs |journal=Computational Complexity Conference |date=2016}}</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="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 |
<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="Allender_1997">{{cite book |
|||
| last = Allender | first = Eric | author-link = Eric Allender |
|||
| editor1-last = Chandru | editor1-first = Vijay |
|||
| editor2-last = Vinay | editor2-first = V. |
|||
| contribution = Circuit complexity before the dawn of the new millennium |
|||
| doi = 10.1007/3-540-62034-6_33 |
|||
| pages = 1–18 |
|||
| publisher = Springer |
|||
| series = Lecture Notes in Computer Science |
|||
| title = Foundations of Software Technology and Theoretical Computer Science, 16th Conference, Hyderabad, India, December 18–20, 1996, Proceedings |
|||
| volume = 1180 |
|||
| year = 1996}}</ref><ref name="Shannon_1949">{{cite journal |author-last=Shannon |author-first=Claude Elwood |author-link=Claude Elwood Shannon |title=The synthesis of two-terminal switching circuits |journal=[[Bell System Technical Journal]] |date=1949 |volume=28| number=1 |pages=59–98 |doi=10.1002/j.1538-7305.1949.tb03624.x}}</ref> |
|||
<ref name="Håstad_1987">{{cite book |author-first=Johan Torkel |author-last=Håstad |author-link=Johan Torkel Håstad |title=Computational limitations of small depth circuits |date=1987 |type=Ph.D. thesis |publisher=Massachusetts Institute of Technology |url=http://www.nada.kth.se/~johanh/thesis.pdf}}</ref> |
|||
| ⚫ | <ref name="Razborov_1985">{{cite |
||
<ref name="Rossman_2008">{{cite conference |author-first=Benjamin E. |author-last=Rossman |author-link=Benjamin E. Rossman |title=On the constant-depth complexity of k-clique |date=2008 |pages=721–730 |book-title=STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing |publisher=[[Association for Computing Machinery]] |doi=10.1145/1374376.1374480}}</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="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 |
<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 |
*{{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] |
*[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] |
*[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] |
||
2024年5月18日 (土) 03:59時点における最新版
回路計算量（英: circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。
概要[編集]
入力が n ビットの論理回路は有向非巡回グラフであり、各ノード（回路計算量の場合、「ゲート」と呼ぶ）は、入次数 0 の入力ノード（n個の入力ビットのいずれかに対応）か、ANDゲート、ORゲート、NOTゲートである。これらのゲートのいずれかが出力ゲートとなる。このような回路が n 個の入力の関数を計算する。回路の大きさは、全ゲート数と、入力ゲートから出力ゲートまでの最大の長さ（すなわち、回路の深さ）で表される。
ブール関数 f の回路計算量（大きさと深さ）は、f を計算する回路のうちで最も小さい回路（あるいは浅い回路）の大きさ（や深さ）で表される。回路計算量の目標は、ブール関数群の最小の大きさや深さを決定することである。n ビット入力の関数 の回路計算量を求める場合、 といった小さい関数から始めて、漸近的に求める手法がよく使われる。
論理回路に関する複雑性クラスとして、AC0、AC、TC0、NCがある。
一様性[編集]
論理回路は一様でない計算模型の典型例であり、入力長が違えば回路も異なる。一方チューリングマシンのような一様な計算模型では、同じ計算機械を任意の入力長に使うことができる。従って、ある計算問題に対応した論理回路は（入力長に従って） のように複数存在し、 の回路は n ビットの入力を扱う。従って一様性はそれら論理回路群全体で成り立つものであり、個々の回路は計算資源を制限したチューリングマシンで計算可能である。
歴史[編集]
Vollmer の 1999年の著書（参考文献参照）によれば、回路計算量の研究に大きな影響を与えたものとして、Savage の1976年の著書[要文献特定詳細情報]が挙げられる。
主な成果[編集]
- ブール関数 PARITY は、入力ビット群の 1 の数が奇数の場合に 1 を返すものだが、 には含まれない。Ajtai（1983）[1][2]と Furst、Saxe、Sipser（1984）[3]がそれぞれ独立に発見した。Hasted（1987）[要文献特定詳細情報]はさらに に属して PARITY を計算する回路は指数関数的な大きさになることを示した。Smolensky（1987）[4]は、入力ビット数を数えて、それを任意の素数で割った余りを出力する回路で同じことが言えることを証明した。
- 単調関数 CLIQUE は多項式サイズの単調回路（否定を使わない、AND と OR だけの回路）では計算できない。Razborov（1985）[5]が最初に発見し、Alon と Boppana（1987）[6]がさらに発展させた。Raz と McKenzie（1999）[7]は、単調NC階層は無限であることを示した。
- 除算はTC0に含まれる（Hesse 2001）[8]。
複雑性クラス[編集]
回路計算量の複雑性クラスの多くはクラス群の階層で定義されている。任意の整数 i について、NCiというクラスが存在し、深さ で入力端子数の制限された AND/OR/NOTゲートを使った多項式サイズの回路が属している。これらのクラスを総称して NC クラスと呼ぶ。入力端子数が無制限のゲートに関しては、ACi とその総称としての AC クラスがある。ゲート数や深さが同じでも、使用するゲートが異なれば、回路計算量の複雑性クラスも異なる。
脚注[編集]
- ^ Ajtai, Miklós (1983). "-formulae on finite structures". Annals of Pure and Applied Logic. 24: 1–24. doi:10.1016/0168-0072(83)90038-6。
- ^ Ajtai, Miklós; Komlós, János; Szemerédi, Endre (1983). "An sorting network". Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA. Association for Computing Machinery. pp. 1–9. doi:10.1145/800061.808726。
- ^ Furst, Merrick L.; Saxe, James Benjamin; Sipser, Michael Fredric (1984). "Parity, circuits, and the polynomial-time hierarchy". Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/BF01744431. MR 0738749. S2CID 6306235。
- ^ Smolensky, Roman (1987). "Algebraic methods in the theory of lower bounds for Boolean circuit complexity". Proceedings of the 19th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery. pp. 77–82. doi:10.1145/28395.28404。
- ^ Razborov, Aleksandr Aleksandrovich (1985). "Lower bounds on the monotone complexity of some Boolean functions". Soviet Mathematics - Doklady. 31: 354–357. ISSN 0197-6788。
- ^ Alon, Noga; Boppana, Ravi B. (1987). "The monotone circuit complexity of Boolean functions". Combinatorica. 7 (1): 1–22. CiteSeerX 10.1.1.300.9623. doi:10.1007/bf02579196. S2CID 17397273。
- ^ Raz, Ran; McKenzie, Pierre (1999). "Separation of the monotone NC hierarchy". Combinatorica. 19 (3): 403–435. doi:10.1007/s004930050062。
- ^ Hesse, William (2001). "Division is in uniform TC0". Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer Verlag. pp. 104–114.
参考文献[編集]
- Vollmer, Heribert (1999). Introduction to Circuit Complexity: a Uniform Approach. Springer Verlag. ISBN 3-540-64310-9。
- 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