並列化とその限界 : 理論的側面から
スポンサーリンク
概要
- 論文の詳細を見る
効率よく並列化できる問題とは,並列ランダムアクセス機械(Parallel RAM)により,多項式個のプロセッサを用いて時間O ((log n)^k) (k>_-0は定数)で計算できる問題と理解されている.そのような問題のクラスは,それを同定したNick Pippengerにちなみ,Nick's Classの略としてNCと記述されている.一方,逐次アルゴリズムにより多項式時間で解ける問題のクラスPは,NCを含んでおり,多くの効率のよい並列アルゴリズムが知られている.しかし,Pのなかには,本質的に逐次的で,並列化が困難な問題も発見されている.そしてこのような問題の大部分がP完全であることが証明されている.ここでは,クラスNCとP完全な問題について解説する.
- 一般社団法人日本ソフトウェア科学会の論文
- 1990-01-16
著者
関連論文
- 正員の例からの最良コンセンサスモチーフの抽出
- アミノ酸配列データからの機械発見システムBONSAI Garden
- 歩行からの次数限定木推論問題
- 最小共通包含木問題に対する並列近似アルゴリズム
- 推論の並列化(計算量理論とその周辺)
- 辞書式順序で最初の極大部分グラフを計算する問題のP完全性とNCアルゴリズム(計算アルゴリズムと計算量の基礎理論)
- 並列知識獲得システムBONSAI Garden
- 形式グラフ体系上の反駁木問題の並列化とグラフ同型問題(計算機構とアルゴリズム)
- BONSAI : 決定木とインデックス化による文字列からの機械発見システム
- Recovery of Incomplete Tables under Data Dependencies (形式言語理論とオ-トマトン理論)
- 並列アルゴリズムの理論
- 並列アルゴリズムの複雑さ
- 並列化とその限界 : 理論的側面から
- 分岐数限定超グラフに対する極大独立集合を求めるNCアルゴリズム
- ゲノム情報における機械学習の計算量 : 理論と実際 (「人工知能技術における計算量」)
- 学習アルゴリズムによるアミノ酸のインデックス化とタンパク質データからの知識獲得実験
- 機械学習理論を適用したアミノ酸配列からの知識獲得
- PAC 学習 : 確率的で近似的に正しい学習 (計算的学習理論とその応用)