組合せ論的問題の計算の複雑さの解析のための新たな手法の開拓

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

P vs. NP問題に代表されるように,問題の計算複雑さの下界を証明することは非常に難しい課題であると言われている.その大きな理由の一つは,下界を解析するための数学的解析技術が十分整っていない点にある.我々はランダムネスと計算の研究の中から,確率的な議論を用いた解析技法や,平均時の解析のアプローチの強化を目指した研究を進めた.その中で本研究では,まず,「Isolation補題の強さについての解析」で結果が得られた.Isolation補題は,NPもしくはNP型解探索問題の計算複雑さの解析において非常に重要な役割を果たす解析手法である.1986年にValiant-Vaziraniが,Isolation補題として,この孤立化の手法を提案して以来,数々の重要な結果が導かれた.そのIsolation補題の強化とその限界は重要な未解決問題である.我々は,いくつかの観点から,Isolation補題がValiant-Vaziraniの提案手法より改善できそうもない,ということを証明することができた.次に「Uniform blackbox algorithmの解析」に関する結果である.上記のIsolation補題の解析では「手法の改善が望めそうもない」ということを示す方法の一つとして,blackbox型のアルゴリズムの限界を述べた.そのアプローチを,より一般的にし,様々な解析技法の限界を統一的に調査する方法としたのが,Uniform blackbox algorithmという概念である.そのような(抽象的)証拠検査手続きに対しても働くアルゴリズムの有無を議論する枠組みである.この枠組みのもと,まずは上記のIsolation補題の限界を,より一般的な形で証明することができた.さらに,我々はNP型解探索アルゴリズムに必要なNP問題への質問回数の下界を情報理論的な解析で同定することができた.