クラスNC

【くらすえぬしい (class NC)】

並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズ$n$の多項式個のプロセッサを使えば, $\log n$の多項式時間でその問題の解を求めることができる. 多項式時間アルゴリズムが存在する問題であっても, 本質的に並列化できないものと, できるものとがある. 並列化することによって効率よく解くことができる問題のクラスがNCである.