0 0

ACC ⁰はACCとも呼ばれ、理論計算機科学の一分野である回路複雑度で定義される計算モデルおよび問題のクラスである。このクラスは、定数深さの「交互回路」のクラスAC ⁰にカウント機能を付加して定義される。頭字語 ACC は「カウンター付き AC」の略である。^[1]具体的には、問題が ACC ⁰に属するのは、固定整数を法としてカウントするゲートを含む、無制限のファンインゲートの多項式サイズ定数深さ回路で解ける場合である。ACC ^{0 は、任意の可解}モノイドにおける計算に対応する。このクラスは、代数的なつながりと、いわゆる回路下限値などの計算不可能性の結果を証明できる最大の具体的な計算モデルの 1 つであるため、理論計算機科学で非常によく研究されている。

非公式には、ACC ^{0 は}、一定の深さと多項式サイズのブール回路によって実現される計算のクラスをモデル化します。回路ゲートには、固定された定数を法として真の入力の数を計算する「モジュラー カウンティング ゲート」が含まれます。

より正式には、言語が AC ⁰ [ m ] に属するのは、回路の族C ₁、C ₂、... によって計算できる場合です。ここで、C _{n は}n 個の入力を受け取り、各回路の深さは一定で、C _nのサイズはnの多項式関数であり、回路は次のゲートを使用します。入力の論理積と論理和を計算する、無制限のファンインのAND ゲートとOR ゲート、単一の入力の否定を計算するNOT ゲート、および入力 1 の数がmの倍数の場合は 1 を計算する、無制限のファンインの MOD- mゲート。言語が ACC ^{0に属するのは、何らかの}mに対して AC ⁰ [ m ]に属する場合です。

いくつかの文献では、ACC ^{iはACC 0を}最下位レベルとする回路クラスの階層を指し、ACC ⁱの回路は深さO（log ⁱ n）と多項式サイズを持ちます。^[1]

クラスACC ^0は、モノイド上の非一様決定性有限オートマトン（NUDFA）の計算の観点から定義することもできます。このフレームワークでは、入力は固定されたモノイドの要素として解釈され、入力要素の積がモノイド要素の指定されたリストに属する場合に入力が受け入れられます。クラスACC ^{0は、部分半群として}解けないグループを含まないモノイド上のNUDFAによって受け入れられる言語の族です。^[2]

クラス ACC ^0にはAC ⁰が含まれる。この包含は厳密である。なぜなら、単一の MOD-2 ゲートは AC ⁰では計算不可能であることが知られているパリティ関数を計算するからである。より一般的には、関数 MOD _{m は、} m がpのべき乗でない限り、素数pに対してAC ⁰ [ p ] では計算できない。^[3]

クラス ACC ^0はTC ⁰に含まれています。ACC ^{0 は}入力の多数決関数を計算できない(つまり、TC ⁰への包含は厳密である) と推測されていますが、これは 2018 年 7 月時点で未解決のままです。

ACC ⁰のすべての問題は、入力に多重対数ファンインの AND ゲートを持ち、対称関数 (入力の順序に依存しない) を計算する単一のゲートに接続された深さ 2 の回路で解決できます。^[4]これらの回路は SYM ^{+回路と呼ばれます。証明は、}戸田の定理の証明の考え方に従います。

Williams (2011)は、ACC ^0にNEXPTIMEが含まれないことを証明しています。この証明では、時間階層定理、IP = PSPACE、デランダム化、SYM ⁺回路によるACC ⁰の表現など、複雑性理論における多くの結果が使用されています。 ^[5] Murray & Williams (2018)はこの境界を改良し、ACC ⁰にNQP（非決定性準多項式時間）が含まれないことを証明しています。

LOGTIME -uniform ACC ^{0回路では}パーマネントを計算することは不可能であることが知られており、これは複雑性クラスPPがLOGTIME-uniform ACC ⁰に含まれないことを意味する。^[6]