到達可能性判定問題の計算量について
スポンサーリンク
概要
- 論文の詳細を見る
無向グラフならびに有向グラフの到着可能性判定問題(各々を, UGAPおよびGAPと略す)は, 1970年代から研究されている古い問題であるが, 領域量が限定された計算過程を具体的な計算問題という形に表現し直したものであり, 領域量に関わる計算量理論にとっては中心的な問題である.本稿ではまず, 無向グラフのパス幅をpw(G)で表すとき, UGAPが決定性O(pw(G)^2logn)領域で判定可能であることを示す.ここで, nは入力として与えられた無向グラフの頂点数を表す.また, これと同じ結果がGAPについても成立する.パス幅は最大でn-1になるので, この結果が極めて良好なものとは言えないが, それでも, パス幅が定数のグラフからなるクラスに対しては, UGAPやGAPが決定性対数領域で判定可能であることを示している.これまで, UGAPやGAPが決定性対数領域で判定可能となるようなクラスとしては無閉路的なグラフ(つまり, 森)のクラス以外には知られていなかった.従って, 本稿の結果はこれ以外の新たなクラスを初めて提示している.更に, 入力を二本の道からなるグラフに制限したとしても, UGAPが決定性対数領域困難(DLOG-hard)になることを示す.この結果は, 入力対象となる無向グラフの構造をどのように制限したとしても, (制限された)UGAPがDLOGより下位のクラス(例えば, NC^1やTC^0など)に属することはないことの強い根拠を与えている.
- 社団法人電子情報通信学会の論文
- 1998-07-23
著者
関連論文
- 2部グラフの部分クラスに対するGI完全性について
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- グラフ同型写像の数え上げ問題に対するアルゴリズム
- [チュートリアル講演]最小値独立置換族に関する最近の成果
- 最小値独立置換族に関する最近の成果
- 有限幾何を用いた線形サイズ4-制限最小値独立置換族の構成
- k-制限最小値独立置換族,その他k-wise独立性のサンプルサイズ下界
- 置換族とその独立性の解析
- 集中討論:DeolalikarのP≠NP論文をめぐって
- 否定数限定論理回路におけるマージングの複雑さ
- Negation-Limited Complexity of Parity and Inverters(Theory of Computer Science and Its Applications)
- Learning DNF by Approximating Inclusion-Exclusion Formulae (Models of Computation and Algorithms)
- 和集合のサイズの近似評価を用いたDNF式の学習について
- あるノイズモデルにおけるブール関数学習について
- フェイステル変換を用いた近似的k-対ランダム置換族の構成
- kトニックな0/1列に対する線形サイズ対数深さの否定数限定インバータ
- ブール関数のsensitivity, block sensitivity, certificate complexity について
- 行列集合の自己同型群を求めるための動的計画アルゴリズム
- 小さな単体成分からなるコーダルグラフの自己同型群を求めるためのアルゴリズム
- 区間グラフの認識アルゴリズムについて
- 到達可能性判定問題の計算量について
- 到達可能性判定問題の計算量について(縮約版) (アルゴリズムと計算の理論)
- 数え上げ計算モデルの計算能力について
- 数え上げ計算モデルの計算能力について
- 計算の複雑さと証明の複雑さ : 基調講演 (証明論と複雑性)
- グラフ同型性判定問題の計算量
- グラフ同型性判定問題の計算量(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 解の個数を数えることの複雑さについて : 数え上げ問題の計算量
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて (離散的アルゴリズムと計算量)
- 正則言語による論理関数の計算量解析 : 群の上で動作するモノイドプログラムについて
- モノイドプログラムによる論理回路計算量クラスの構造解析