AC
#計算複雑性理論
#計算複雑性クラス
#Boolean回路
定義
$ \mathbf{AC}^d
$ L \in \mathbf{AC}^d \iff \text{$L$を表現する深さ$d$以下の多項式サイズのfan-in無制限の回路$\{C_n\}_n$が存在する}
$ \mathbf{AC}
$ \mathbf{AC} := \bigcup_d \mathbf{AC}^d
関連
NC