NC (計算複雑性理論)

計算複雑性理論において、NC（Nick's Class）とは多項式個数のプロセッサで構成される並列計算機で，問題サイズの対数について多項式時間で解ける決定問題の複雑性クラスである。換言すれば、NC に属する問題は、O(n^k)個の並列プロセッサを使って O((log n)^c) の時間で解ける（c と k は定数）。"Nick's Class" という用語はスティーブン・クックの造語で、計算機科学者 Nick Pippenger にちなんでいる。

クラス P と同様、NC に属する問題は並列計算機で効率的に解くことができると見なされている。並列計算機は通常の計算機でシミュレート可能であるため、NC は P に含まれる。NC = P かどうかは判っていないが、おそらく違うだろうと言われている。つまり、多項式時間で解ける問題には「本質的に逐次的」なものがあり、並列化によって高速化できないと考えられている。NP完全問題は効率的に解けないと考えられているように、P完全問題は「本質的に並列化不可能」または「本質的に逐次的」であると考えられている。

この定義における並列計算機は「並列ランダムアクセス機械」（PRAM）である。これは、共有メモリ型の並列計算機の計算モデルで、全プロセッサがどのメモリ位置についても一定の時間でアクセスできるものと定義されている。NC の定義は PRAM において複数のプロセッサが同じメモリ位置にアクセスした場合の対処方法には影響されない。この排他モデルとして CRCW、CREW、EREW がある。詳しくはPRAMを参照されたい。

NC の別の定義として、対数多項式の深さと多項式個の論理ゲートからなる一様ブール回路で解ける決定問題の集合という定義もある。

NCⁱ は、多項式個の論理ゲートからなる一様ブール回路（深さ O((log n)ⁱ)）で解ける決定問題の集合である。また、多項式個のプロセッサからなる並列計算機上で O((log n)ⁱ) 時間で解ける決定問題の集合でもある。

NC クラス群と L および NL の関係は Papadimitriou 1994, Theorem 16.1 により次のように示される。

[math] \mathbf{NC^1 \subseteq L \subseteq NL \subseteq NC^2} [/math]

同様に、NCⁱ は、交替性チューリングマシンで O(log n) の領域と (log n)^O(1) 回の交替で解ける決定問題の集合と同じである。

参考文献

• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4
• Heribert Vollmer. Introduction to Circuit Complexity -- A Uniform Approach. ISBN 3-540-64310-9
• Christos Papadimitriou (1993年). Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1.  Section 15.3: The class NC, pp.375–381.
• Dexter Kozen (2006年). Theory of Computation. Springer. ISBN 1-84628-297-7.  Lecture 12: Relation of NC to Time-Space Classes