表題番号：2006B-073
日付：2007/03/21
研究課題計算量の階層を特徴付ける単一問題の研究
| 研究者所属（当時） | 資格 | 氏名 | |
|---|---|---|---|
| （代表者） | 教育・総合科学学術院 | 教授 | 守屋 悦朗 |
- 研究成果概要
- 研究代表者は従来より、ある組合せ論的問題１つから様々な変形版が自然に導入でき、しかもそれらが計算量の階層の中でも重要ないくつものクラスの完全問題になるようなものを発見することを目指してきた。Ｌ⊆ＮＬ⊆Ｐ⊆ＮＰ⊆ＰＳＰＡＣＥ⊆ＥＸＰ⊆ＮＥＸＰ⊆・・・といった計算量の階層のいくつかに対する完全問題を自然に導く組合せ論的問題の例としてはＳＡＴやＨＣＰ、あるいはAdachi-Iwata-Kasaiによる有効グラフ上の石置きゲームに関する結果
[2] A.Adachi, S.Iwata and T.Kasai, Classes of pebble games and complete problems, SIAM J. Comput. 8 (1979), 574--586.
等が知られているが、単にこういった決定問題に対する計算量の階層の各クラスを表すような変形版が自然に導入できるというにとどまらず、数え上げ版や最適化版（近似問題版）の計算量の各クラス、例えば、＃Ｐ，ＡＰＸ，ＮＰＯ，ＰＴＡＳ，ＦＰＴＡＳといったクラスをも表わすような１つの組合せ論的問題を発見することが目標であった。具体的には、研究代表者自らの先駆的研究
T.Nishida and E.Moriya, Variants of the subgraph connecting problem and their computational complexity, Tech. Rept. of IEICE 103, 2004, 1－7.
を出発点とし、すでに当初目標に沿ったいくつかの成果をあげてきた。その元となっている問題 "Subgraph Connecting Problem" とは、グラフ G とその部分グラフのいくつかが与えられたとき、各部分グラフと1点だけを共有して連結な G の部分グラフを求める問題である。本研究では近似問題のうちでまだ具体例が知られていなかったＰＴＡＳおよびＦＰＴＡＳに属す問題を見つけた。それは、グラフ G=(V,E) とその部分グラフ G1, ・・・, Gm, 頂点に対する重み関数 w : V(G)→N と定数 k∈N が与えられたとき、|V(G')∩V(Gi)|>0 for ∀i かつ ∑v∈V(G')w(v)≦k という条件の下で頂点の重みの和が最小となるような G の部分グラフ G' を求める問題である。
なお、本研究の基礎ともなるオートマトン・言語理論にも取り組み、alternation （交代性）の概念を取り入れた形式文法とその拡張にに関しても成果を挙げた。