AC（複雑さ）

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

「AC」という名前はNCとの類推から選ばれました。名前の「A」は「交互」を意味し、回路内のANDゲートとORゲートの交互動作と、交互チューリングマシンの両方を指しています。^[1]

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

ACクラスの階層全体は次のように定義される。

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

NCとの関係

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]

となる。特に、PARITYは に含まれるが には含まれない。^[4]また、NCは制限付きファンインを要求するため、出力が 個以上の入力に依存する 型の関数は を超える。特に、制限なしファンインORは を超える。 ${\displaystyle {\mathsf {NC}}^{0}\subsetneq {\mathsf {AC}}^{0}\subsetneq {\mathsf {ACC}}^{0}}$ ${\displaystyle {\mathsf {ACC}}^{0}}$ ${\displaystyle {\mathsf {AC}}^{0}}$ ${\displaystyle \{0,1\}^{n}\to \{0,1\}}$ ${\displaystyle O(1)}$ ${\displaystyle {\mathsf {NC}}^{0}}$ ${\displaystyle {\mathsf {NC}}^{0}}$

詳細には、によって定義されます。すると、ゲートは深さ の回路によって計算される必要があります。^[5] ${\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}$

バリエーション

ACクラスの能力は、ゲートの追加によって影響を受ける可能性があります。ある法mに対する剰余演算を計算するゲートを追加すると、クラスACC ⁱ [m]が得られます。^[3]

注記

1. リーガン（1999年）、27-18ページ。
2. Clote & Kranakis (2002)、437ページ; Arora & Barak (2009)、118ページ。
3. Clote & Kranakis (2002)、12ページ。
4. ラズボロフ (1987).
5. ピタッシ (2015).

参考文献

• アローラ、サンジーヴ；バラク、ボアズ（2009年）、計算複雑性：現代的アプローチ、ケンブリッジ大学出版局、ISBN 978-0-521-42426-4、Zbl  1193.68112
• Clote, Peter; Kranakis, Evangelos (2002),ブール関数と計算モデル, Texts in Theoretical Computer Science: An EATCS Series, ベルリン: Springer-Verlag , ISBN 3-540-59436-1、Zbl  1016.94046
• ピタッシ、トニアン（2015年秋）​​、「講義＃8」（PDF）、CS 2401 - 複雑性理論入門、トロント大学
• ラズボロフ, AA (1987年4月)、「論理加算を伴う完全基底上の境界付き深度回路のサイズの下限」、ソ連科学アカデミー数学ノート、41 (4): 333– 338、doi :10.1007/BF01137685、ISSN  0001-4346
• リーガン、ケネス・W.（1999）「計算量クラス」、アルゴリズムと計算理論ハンドブック、CRCプレス。
• Vollmer, Heribert (1998), 『回路計算量入門：統一的アプローチ』 Texts in Theoretical Computer Science, Berlin: Springer-Verlag , ISBN 3-540-64310-9、Zbl  0931.68055

「https://en.wikipedia.org/w/index.php?title=AC_(complexity)&oldid=1312462261」より取得