NC (計算複雑性理論)

計算複雑性理論におけるNCクラスについて

計算複雑性理論におけるNC（Nick's Class）は、並列計算において多項式個のプロセッサを用いて解決できる決定問題のクラスを指します。具体的には、問題のサイズの対数に対する多項式時間で解ける問題がNCに属します。これを別の言い方をすると、O(n^k)個の並列プロセッサを使用して、O((log n)^c)の時間で解決可能であるということです。このとき、cおよびkは定数です。NCという名称は計算機科学者のNick Pippengerにちなんでおり、スティーブン・クックによって造られた用語です。

NCとPクラスの関係

NCに分類される問題は、クラスPに属する問題と同じく、効率的に解決できると見なされます。これは、一般的な計算機が並列計算機をシミュレートできるため、NCはPに含まれるという事実から来ています。ただし、NCとPが等しいかどうかは依然として不明であり、現在のところ異なると考えられています。このことは、多項式時間で解決可能な問題には「本質的に逐次的」なものが存在し、並列処理によっても高速化が難しいという見解に関連しています。

NP完全問題が効率的に解けないとされるように、P完全問題もまた「本質的に並列化不可能」または「本質的に逐次的」であると考えられています。このように、計算複雑性においてはそれぞれのクラスが持つ性質に基づいて分類されています。

PRAMモデルによるNCの定義

NCの定義は、「並列ランダムアクセス機械」（PRAM）モデルに基づいています。PRAMは共有メモリ型の並列計算機のモデルであり、すべてのプロセッサが任意のメモリ位置に対して定時間でアクセスできると定義されています。この時、複数のプロセッサが同時に同じメモリ位置にアクセスした場合の処理方法には、いくつかの排他制御モデルがあり、CRCW（Concurrent Read, Concurrent Write）、CREW（Concurrent Read, Exclusive Write）、EREW（Exclusive Read, Exclusive Write）が存在します。

NCのもう一つの定義には、対数が多項式の深さと多項式個の論理ゲートから構成された一様ブール回路で解決可能な決定問題の集合があります。このNCiは、深さO((log n)^i)の一様ブール回路で解決する決定問題の集まりを示します。これにより、多項式個のプロセッサを使ってO((log n)^i)の時間で解ける問題が定義されています。

NCと他の複雑性クラスとの関係

NCクラスとLおよびNLの間の関係については、Papadimitriouによって示された定理により定義されています。具体的には、次のように表現されます。

$$ NC^1 \\ \subseteq L \\ \subseteq NL \\ \subseteq NC^2 $$

このように、NCは他のクラスとの比較において、交替性チューリングマシンを用いた解決方法とも関連しています。これによって、O(log n)の領域における決定問題を効率的に扱う方法を知ることができます。

参考文献

• - 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

もう一度検索