FP^<NP>_>||>のある特徴付けと完全問題
スポンサーリンク
概要
- 論文の詳細を見る
最近の計算量理論では,従来の言語のクラスに基づく研究から関数のクラスに基づく研究へと移行しつつある.この動きの中で,NPに属する言語をオラクルとして用いる多項式時間アルゴリズムによって計算される関数のクラスの研究が盛んに行われるようになっている.このようなクラスの代表として,FP^NP[log]>FP^NP>およびEP^NP>_||>がある.これまでの研究によって,EP^NP[log]>やFP^NP>に関してよい特徴付けが示され,これらのクラスの意義が見いだされている.一方,FP^NP>_||>については,技術的にはその有用性が認められているにもかかわらず,その直観的な意義はまだ見い出されていない.本研究では,このクラスの興味ある特徴付けを与え,FP^NP>_||>に対して自然な完全問題を示す.例えば,グラフGが与えられたとき,Gのどのハミルトン閉路にも含まれないような辺全てを除去したGの部分グラフを計算する問題はFP^NP>_||>完全になる.
- 一般社団法人電子情報通信学会の論文
- 1993-06-25
著者
関連論文
- 極大無閉路集合を求める並列アルゴリズム
- 一般化された剰余型計算量クラスの計算量について
- VLSIモデルへのグラフの埋め込みについて(計算機構に関する数学的基礎理論とその応用)
- 最小切点集合を求めるための$O(N^2)$アルゴリズム (形式言語理論とオートマトン理論)
- FP^_>||>のある特徴付けと完全問題
- 実際的計算可能性の拡張について
- 確率的多項式時間アルゴリズムの能力について(計算アルゴリズムと計算量の基礎理論)