「クラスNC」の版間の差分
ナビゲーションに移動
検索に移動
細 ("クラスNC" を保護しました。 [edit=sysop:move=sysop]) |
|
(相違点なし)
| |
2007年7月20日 (金) 09:33時点における版
【くらすえぬしい (class NC)】
並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズの多項式個のプロセッサを使えば, の多項式時間でその問題の解を求めることができる. 多項式時間アルゴリズムが存在する問題であっても, 本質的に並列化できないものと, できるものとがある. 並列化することによって効率よく解くことができる問題のクラスがNCである.
