並列複雑さが徐々に変化する問題について
スポンサーリンク
概要
- 論文の詳細を見る
より難しい問題には,より多くの計算時間が必要となることは,直観的に明らかである.実際,逐次計算に関しては,計算時間の上限を大きくすればするほど,受理できる言語のクラスは大きくなるという階層定理が知られている.それに対し,並列計算に関しては,言語のクラスの時間的階層性は,ほとんど何も分かっていない.nの多項式台のプロセッサを持つ並列計算機モデルを用いてlog nの多項式時間で解ける問題のクラスはNCと呼ばれ,さらに,log nの何乗の時間で解けるかという観点から,NCには,NC^1⊆NC^2⊆…⊆NCなる包含関係がある.(厳密には,クラスNC^kは,対数領域一様な論理回路族の段数で定義される.)並列計算における時間量の階層については,NC^k⪿NC^k+1が未解決であるだけでなく,さらに,NC^1⪿NPの証明さえも分かっておらず,このことは階層性の証明が非常に難しいことを物語っている.しかし,並列計算においても,より難しい問題にはより多くの計算時間がかかることは,直観的に明らかであり,このことを如何に合理的に説明できるかが,並列計算理論の分野での重要な課題になっている.本稿では,並列計算時間が徐々に上昇する問題と徐々に減少する問題の例を挙げ,いかに「合理的説明」が可能であるかを紹介する.具体的には,(i)単一のパラメータ値の増加に従って,計算複雑さがクラスNCからP完全まで徐々に上昇するグラフ問題が存在すること,(ii)多項式台のプロセッサを持つ並列計算機で非常に微小な並列時間で解けるが,定数時間では解けない(人工的な)問題が存在し,その計算時間を限りなく小さくできることを紹介する.
- 社団法人電子情報通信学会の論文
- 1996-03-11
著者
関連論文
- 並列複雑さが徐々に変化する問題について
- テープ記号数を制限した決定性TMと交代性TMの領域計算量について
- CRCW PRAMの時間計算量の稠密な階層
- 並列計算用に拡張したTMの時間計算量の階層
- チューリング機械の領域計算量の厳密な階層について(計算理論とその応用)
- テープ記号数を制限した領域限定TMの階層について
- PRAMおよび対数時間一様な論理回路族に基づく計算量の階層(計算モデルと計算の複雑さに関する研究)