NC (計算複雑性理論)
NC の定義は PRAM において複数のプロセッサが同じメモリ位置にアクセスした場合の対処方法には影響されない。この排他モデルとして CRCW、CREW、EREW がある。詳しくはPRAMを参照されたい。
NC の別の定義として、対数多項式の深さと多項式個の論理ゲートからなる一様ブール回路で解ける決定問題の集合という定義もある。
NC は、多項式個の論理ゲートからなる一様ブール回路(深さ O((log n)))で解ける決定問題の集合である。また、多項式個のプロセッサからなる並列計算機上で O((log n)) 時間で解ける決定問題の集合でもある。
NC クラス群と L および NL の関係は Papadimitriou 1994, Theorem 16.1 により次のように示される。
N C 1 ⊆ L ⊆ N L ⊆ N C 2 {\displaystyle \mathbf {NC^{1}\subseteq L\subseteq NL\subseteq NC^{2}} }
同様に、NC は、交替性チューリングマシンで O(log n) の領域と (log n) 回の交替で解ける決定問題の集合と同じである。