RS型ベクトル機械上での幾つかの具体的問題に対するアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
ベクトル機械は、種種のベクトル命令セットがどのような能力を持つかという観点から、幾つかの論文で論じられてきた([1][2][4]等)。文献[2]は、並列モデルの局所計算と通信をより明確に分離するため、ベクトル機械の命令セットとして、要素ごとの加減演算(局所計算に対応)や、ベクトルを拡大する2種類のrepeat.stretch演算ならびにそれらの逆演算(通信に対応)を導入した。repeatは、例えばベクトル(a1,a2,…,am)を(a1,a2,…,am,a1,a2,…,am)に、stretchは(a1,a1,a2,a2,…,am,am)にする演算である。このベクトル機械(RS型ベクトル機械)は、上記演算の拡大縮小の度合(拡大率)を変化することにより、異なった能力のベクルル機械を作れることが知られている。より詳しくは、拡大率2のとき、TMの多項式領域を多項式時間量に、拡大率mのとき、ATMの指数時間多項式交代数を多項式時間量に加速する能力がある。さらに、文献[3]は、拡大率2はkに、mはcmkに置き換わることを示し、拡大率が指数的に大きくなったときの能力についても考察している。このようにRS型ベクトル機械の能力については、多項式時間という大雑把な鐘囲内での一般的シミュレーションに限定すればかなり明らかになったといえる。本稿では拡大率が2のRS型ベクトル機械を用いて具体的なNP完全問題を高速に解くアルゴリズムを紹介する。2.でRS型ベクトル機械の説明を行ない、3.で充足可能性問圏をO(n)時間で、4.でハミルトン閉路問題をO(nlog2n)時間で解くアルゴリズムを紹介する
- 1991-02-25
著者
関連論文
- A note on tatami tilings (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 非決定性チューリング機械の厳密な領域階層定理(情報・システム基礎)
- 交代性計算によるセルオートマトンの加速
- NP完全集合によるco-NP完全集合の近似
- 充足可能性問題に対する計数法の項の選択による高速化
- グラフの色ぬり分け問題からSATへの効率の良い変換方法とその評価
- RS型ベクトル機械上での幾つかの具体的問題に対するアルゴリズム
- 段数を制限したドミノタイリングの効率良い再構成アルゴリズム(アルゴリズム理論)
- 計算万能な双曲セル・オートマトンについて (計算機科学基礎理論とその応用)
- 一変数テーブル参照による保存的セル・オートマトンの論理万能性
- 「高度応用のための情報ベースモデルとその実現技術」を目指して (メディア統合および環境統合のための高機能データベースシステム、および一般)
- ブロック同期方式による並列アルゴリズムの記述とそのプログラム化
- 一意並列解析可能ユニフィケーション文法 (計算モデルとアルゴリズム)
- ブロック同期に基づく並列アルゴリズムアニメーションシステム
- 充足可能性問題に対する計数法の変数の選択による改良
- Number conservingなセル空間での自己増殖 (計算理論とアルゴリズムの新展開)
- 3次元一意解析可能アレイ文法による図形の生成と認識について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 2点スプライシングシステムの言語生成能力の万能性(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- Two-Point Splicing Systemの言語生成能力の万能性 (計算モデルとアルゴリズム)
- 正則グラフに対する密な部分グラフ問題
- 非決定性回路族における深さと非決定性ゲート数の関係
- ファンイン制限つき組合せ論理回路に対する完全な等価変換規則集合
- 素子制限のある論理回路を等価変換するための基本操作集合について
- ランダムベンチマーク例題による論理最適化システムの評価
- ランダムベンチマーク例題による論理最適化システムの評価
- 論理最適化アルゴリズム評価のためのテスト例題のランダム生成
- 論理最適化アルゴリズム評価のためのテスト例題のランダム生成
- 論理回路簡単化問題に対する例題生成
- 一切の情報を漏らさずプログラムの正当性を証明する方法
- 差分法の任意形状格子メッシュへの適用に関する検討
- テープ記号数を制限したチューリング機械の領域階層
- 総合電機メーカにみる戦後50年の技術変遷と景気変動の影響
- テープ記号数を制限した決定性TMと交代性TMの領域計算量について
- CRCW PRAMの時間計算量の稠密な階層
- 並列計算用に拡張したTMの時間計算量の階層
- チューリング機械の領域計算量の厳密な階層について(計算理論とその応用)
- テープ記号数を制限した領域限定TMの階層について
- CNF論理式に対する局所探索法の項の追加による改良
- リテラルの出現回数を制限した充足不能な3CNF式
- リテラル出現回数が2回の充足不能な3SAT式
- 確率的手法によるCRCW PRAM間の模倣について
- メッシュバス上での最小全域木アルゴリズム
- グラフの最小全域木を求めるためのメッシュバス上での並列アルゴリズム
- 最大値問題に対するメッシュバス上でのO((log log n)^2)アルゴリズム
- ランダムアクセス機能を持つ並列TMの時間計算量の階層
- PRAMおよび対数時間一様な論理回路族に基づく計算量の階層(計算モデルと計算の複雑さに関する研究)
- $\alpha$連結成分問題の計算複雑さの上昇について(計算量理論)
- On Parallelizability of α-Connectivity
- 並列化が徐々に困難になるグラフ問題について
- 色塗り分け問題がP完全又はNCになる為の十分条件について(理論計算機科学とその周辺)
- 組合せ問題に対する RS 型ベクトルアルゴリズム
- RS型ベクトル機械の実際的応用の可能性について(計算および計算量理論とその周辺)
- 多面体テラインの面警備員数の上下限の改善(研究速報)
- 密な部分グラフ問題のNP完全性とそのSAT例題生成への応用
- AIMジェネレータによるバックトラック及び局所探索SATアルゴリズムの評価