テープ記号数を制限した決定性TMと交代性TMの領域計算量について
スポンサーリンク
概要
- 論文の詳細を見る
計算量クラスを分離することは, 計算量理論の分野において最も重要な研究課題の一つである。決定性や非決定性, 交代性の領域量や時間量の関係については, 古くから数多くの研究結果が知られてきた。例えば, 決定性時間量については, t_2(n)がt_1(n)logt_1(n)よりも真に成長が速い関数とすると, DTIME(t_1(n))⊊DTIME(t_2(n))なる階層性が存在することが知られている。また, 決定性領域量や交代性時間量に対する決定性時間量の分離として, DTIME(t(n))⊊DSPACE(t(n))や, DTIME(t(n))⊊ATIME(t(n))などが示されでいる。一方, 非決定性時間量に対する決定性時間量の分離では, DTIME(n)⊊NTIME(n)が証明されているが, 一般のk>1に対してDTIME(n^k)⊊?NTIME(n^k)と拡張できるかについては未解決である。最近になって, 交代性時間量に対する決定性時間量の分離は, DTlME(t(n))⊊Σ_2(t(n))のように交代数が2回に改善されている。その一方, テープ数が1の場合は, (t(n))^<2/3>log^2t(n)時間の交代性TMはt(n)時間の決定性TMを模倣できるという逆の結果も示されている。一方, 決定性領域量については,非決定性や交代性といった機能を使わなくても, 計算量をほんの少し増加させるだけで, クラスを分離できることが知られている。s_2(n)がs_1(n)より成長が真に速い関数とすると, DSPACE(s_1(n))⊊DSPACE(s_2(n))なる階層性が存在することが知られている。テープ圧縮定理が成立するので, この階層性は最適であるといえる。本稿では, テープ記号数を固定して領域計算量クラスの厳密な分離を試みる。如何なる関数ψ(n)≠O(1)に対しても, s(n)領域の決定性TMはs(n)+ψ(n)領域の交代性TMより能力が真に低いことを示す。以下, 節2にてモデルと結果を与え, 節3にて証明の概略を与える。
- 一般社団法人情報処理学会の論文
- 1997-09-24
著者
関連論文
- A note on tatami tilings (アルゴリズムと計算機科学の数理的基盤とその応用--RIMS研究集会報告集)
- 非決定性チューリング機械の厳密な領域階層定理(情報・システム基礎)
- 交代性計算によるセルオートマトンの加速
- RS型ベクトル機械上での幾つかの具体的問題に対するアルゴリズム
- 段数を制限したドミノタイリングの効率良い再構成アルゴリズム(アルゴリズム理論)
- 計算万能な双曲セル・オートマトンについて (計算機科学基礎理論とその応用)
- 一変数テーブル参照による保存的セル・オートマトンの論理万能性
- 一意並列解析可能ユニフィケーション文法 (計算モデルとアルゴリズム)
- ランダムに生成された和積形論理式が充足不能となるしきい値について (アルゴリズムと計算の理論)
- Low-Level Tradeoffs between Cross And Alternation(Algorithms : Mathematical Foundations and Applications)
- 解の存在が保障されている組合せ探索問題について(計算機科学の基礎理論とその応用)
- シャフルされた記号列の復元問題 (形式言語理論とオートマトン理論)
- 自己シャフルに関する判定問題について (数理情報科学の基礎理論と応用)
- 2入出カ対オートマトンによる計算機結合インタフェースの設計手順 (計算機構の数学的研究)
- 並列複雑さが徐々に変化する問題について
- 2次元メッシュバス上での高速な確率ラウティングアルゴリズム
- 2次元メッシュバス並列計算機上での確率ラウティングアルゴリズム
- Number conservingなセル空間での自己増殖 (計算理論とアルゴリズムの新展開)
- 3次元一意解析可能アレイ文法による図形の生成と認識について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 2点スプライシングシステムの言語生成能力の万能性(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- Two-Point Splicing Systemの言語生成能力の万能性 (計算モデルとアルゴリズム)
- 非決定性回路族における深さと非決定性ゲート数の関係
- 為替交換問題に対する最適に近いオンラインアルゴリズムの設計と解析
- 為替交換問題に対するオンラインアルゴリズムの効率解析
- 差分法の任意形状格子メッシュへの適用に関する検討
- テープ記号数を制限したチューリング機械の領域階層
- 総合電機メーカにみる戦後50年の技術変遷と景気変動の影響
- テープ記号数を制限した決定性TMと交代性TMの領域計算量について
- CRCW PRAMの時間計算量の稠密な階層
- 並列計算用に拡張したTMの時間計算量の階層
- チューリング機械の領域計算量の厳密な階層について(計算理論とその応用)
- テープ記号数を制限した領域限定TMの階層について
- 確率的手法によるCRCW PRAM間の模倣について
- ランダムアクセス機能を持つ並列TMの時間計算量の階層
- PRAMおよび対数時間一様な論理回路族に基づく計算量の階層(計算モデルと計算の複雑さに関する研究)
- $\alpha$連結成分問題の計算複雑さの上昇について(計算量理論)
- On Parallelizability of α-Connectivity
- 並列化が徐々に困難になるグラフ問題について
- 色塗り分け問題がP完全又はNCになる為の十分条件について(理論計算機科学とその周辺)
- 組合せ問題に対する RS 型ベクトルアルゴリズム
- RS型ベクトル機械の実際的応用の可能性について(計算および計算量理論とその周辺)
- 多面体テラインの面警備員数の上下限の改善(研究速報)