拡張されたチューリングマシンモデルを用いた各種のアルゴリズムの研究

点击翻译按钮获取中文摘要

本研究の目的は、従来の計算量の理論の分野で手に負えないとされてきた問題に対して、妥当な拡張を行った計算モデルを使い、ある程度条件を緩めた解を求めることであった。具体的には以下のようなアプローチを行い、それぞれの結果を得た。1.確率的なアルゴリズムを中心にすえるアプローチ:グラフ上の極大パス集合を求める、並列アルゴリズムを構成し、その応用について示した。また、部分的に故障した回路の故障個所を特定する問題を考えた。そして代表的なケースについて、理論的な下界を求め、それらに近い振る舞いを示す実際のアルゴリズムを構成して、上界を示した。2.手に負えない、とされてきた問題に対して、解の大きさを限定するなど、もっと粒度の細かい尺度を用いて、現実的な解決をめざしたアプローチ:グラフ上のいくつかの問題に対して、その解の候補の大きさを制限した場合についての結果を得た。3.問題の並列性の評価を考察するアプローチ:並列計算において手に負えない、とされてきた問題に対して、どのような場合ならば手に負えるか、考察を行った。具体的には、与えられたグラフの辞書式順序最小の極大独立点を求める問題をとりあげた。そして、最長有向パス長というパラメータを使えば、この問題の並列性をある程度評価できることを示した。また一方でこのパラメータが他の問題では限界があることや、Random Graphと呼ばれるグラフではあまりうまく機能しないことも示した。