「クラスNC」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【くらすえぬしい (class NC)】''' 並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
'''【くらすえぬしい (class NC)】''' | '''【くらすえぬしい (class NC)】''' | ||
| − | 並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズ | + | 並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズ<math>n\,</math>の多項式個のプロセッサを使えば, <math>\log n\,</math>の多項式時間でその問題の解を求めることができる. 多項式時間アルゴリズムが存在する問題であっても, 本質的に並列化できないものと, できるものとがある. 並列化することによって効率よく解くことができる問題のクラスがNCである. |
| + | |||
| + | [[Category:組合せ最適化|くらすえぬしい]] | ||
2008年11月8日 (土) 19:41時点における最新版
【くらすえぬしい (class NC)】
並列計算により解答を効率よく求めることができる問題のクラスの1つ. ある問題がクラスNCに属するときには, 入力サイズの多項式個のプロセッサを使えば, の多項式時間でその問題の解を求めることができる. 多項式時間アルゴリズムが存在する問題であっても, 本質的に並列化できないものと, できるものとがある. 並列化することによって効率よく解くことができる問題のクラスがNCである.
