「クラスNC」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【くらすえぬしい (class NC)】''' 並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属...') |
|||
| 1行目: | 1行目: | ||
'''【くらすえぬしい (class NC)】''' | '''【くらすえぬしい (class NC)】''' | ||
| − | 並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズ | + | 並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズ<math>n\,</math>の多項式個のプロセッサを使えば, <math>\log n\,</math>の多項式時間でその問題の解を求めることができる. 多項式時間アルゴリズムが存在する問題であっても, 本質的に並列化できないものと, できるものとがある. 並列化することによって効率よく解くことができる問題のクラスがNCである. |
2007年7月12日 (木) 03:00時点における版
【くらすえぬしい (class NC)】
並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズの多項式個のプロセッサを使えば, の多項式時間でその問題の解を求めることができる. 多項式時間アルゴリズムが存在する問題であっても, 本質的に並列化できないものと, できるものとがある. 並列化することによって効率よく解くことができる問題のクラスがNCである.
