NC (計算複雑性理論)
計算複雑性理論において、NC(Nick's Class)とは多項式個数のプロセッサで構成される並列計算機で,問題サイズの対数について多項式時間で解ける決定問題の複雑性クラスである。換言すれば、NC に属する問題は、O(n)個の並列プロセッサを使って O((log n)) の時間で解ける(c と k は定数)。"Nick's Class" という用語はスティーブン・クックの造語で、計算機科学者 Nick Pippenger にちなんでいる。
クラス P と同様、NC に属する問題は並列計算機で効率的に解くことができると見なされている。並列計算機は通常の計算機でシミュレート可能であるため、NC は P に含まれる。NC = P かどうかは判っていないが、おそらく違うだろうと言われている。つまり、多項式時間で解ける問題には「本質的に逐次的」なものがあり、並列化によって高速化できないと考えられている。NP完全問題は効率的に解けないと考えられているように、P完全問題は「本質的に並列化不可能」または「本質的に逐次的」であると考えられている。
この定義における並列計算機は「並列ランダムアクセス機械」(PRAM)である。これは、共有メモリ型の並列計算機の計算モデルで、全プロセッサがどのメモリ位置についても一定の時間でアクセスできるものと定義されている。