AC（複雑性）

回路複雑性において、ACは複雑性クラスの階層構造です。各クラスAC ⁱは、深さを持つブール回路によって認識される言語で構成されます。${\displaystyle O(\log ^{i}n)}$そして、多項式数個の無制限のファンインANDゲートとORゲート。

「AC」という名称はNCになぞらえて選ばれたもので、名称の「A」は「交互」を意味し、回路内のANDゲートとORゲートの交互動作と交互動作チューリングマシンの両方を指している。^{[ 1 ]}

最小のACクラスはAC ⁰で、これは定深度無制限のファンイン回路で構成されます。

ACクラスの階層構造全体は次のように定義されます。

${\displaystyle {\mbox{AC}}=\bigcup _{i\geq 0}{\mbox{AC}}^{i}}$

AC クラスはNC、ACC、およびTCクラスに関連しています。各iについて、^{[ 2 ]}

${\displaystyle {\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {ACC}}^{i}\subseteq {\mathsf {TC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.}$

このことから、NC = AC = ACC = TC が成り立つ。^{[ 3 ]}

我々は持っています${\displaystyle {\mathsf {NC}}^{0}\subsetneq {\mathsf {AC}}^{0}\subsetneq {\mathsf {ACC}}^{0}}$具体的には、PARITYは${\displaystyle {\mathsf {ACC}}^{0}}$しかし、${\displaystyle {\mathsf {AC}}^{0}}$^{[ 4 ]}また、NCはファンインの制限を要求するため、型が${\displaystyle \{0,1\}^{n}\to \{0,1\}}$その出力は、${\displaystyle O(1)}$入力は${\displaystyle {\mathsf {NC}}^{0}}$特に、無制限のファンインORは${\displaystyle {\mathsf {NC}}^{0}}$。

詳細に定義する${\displaystyle f_{n}:\{0,1\}^{n}\to \{0,1\}}$による${\displaystyle f_{n}(x_{1},\dots ,x_{n})=\sum _{i}x_{i}\mod 2}$すると、${\displaystyle \Omega (2^{\frac {n^{1/d}}{16}})}$ゲートは、${\displaystyle {\mathsf {AC}}^{0}}$深さのある回路${\displaystyle \leq d}$[ ^{5 ]​}

AC クラスのパワーは、追加のゲートを追加することで影響を受ける可能性があります。ある法mの剰余演算を計算するゲートを追加すると、クラスACC ⁱ [m]が得られます。^{[ 3 ]}

• Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press , ISBN 978-0-521-42426-4、Zbl 1193.68112 
• Clote, Peter; Kranakis, Evangelos (2002)、ブール関数と計算モデル、理論計算機科学テキスト：EATCSシリーズ、ベルリン：Springer-Verlag、ISBN 3-540-59436-1、Zbl 1016.94046 
• ピタッシ、トニアン（2015年秋）​​、「講義第8回」（PDF）、CS 2401 – 複雑性理論入門、トロント大学
• Razborov, AA (1987年4月)、「論理加算を伴う完全基底上の有界深さ回路のサイズの下限」、ソ連科学アカデミー数学ノート、41 (4): 333–338、doi : 10.1007/BF01137685、ISSN 0001-4346 
• リーガン、ケネス・W. (1999)、「複雑性クラス」、アルゴリズムと計算理論ハンドブック、CRC Press。
• Vollmer, Heribert (1998), 『回路複雑性入門：統一的アプローチ』 , Texts in Theoretical Computer Science, Berlin: Springer-Verlag , ISBN 3-540-64310-9、Zbl 0931.68055