NC
NC, Nick's Class
定義
$ \mathbf{NC}^d
$ L \in \mathbf{NC}^d \iff \text{$L$を表現する深さ$d$以下の多項式サイズの回路$\{C_n\}_n$が存在する}
$ \mathbf{NC}
$ \mathbf{NC} := \bigcup_d \mathbf{NC}^d
効率的な並列アルゴリズムを表現するクラス
性質
$ \mathbf{NC}^d \subseteq \mathbf{AC}^d \subseteq \mathbf{NC}^{d+1}
ACの$ nfan-in無制限の論理式$ \bigwedge_{i < n} c_iや$ \bigvee_{i < n} c_iはNCの$ O(\log n)サイズの回路で表現できるから $ \mathbf{NC} = \mathbf{AC}
上よりあきらか
関連