著者

井原 俊輔

出版者

京都大学数理解析研究所

雑誌

数理解析研究所講究録 (ISSN:18802818)

巻号頁・発行日

vol.975, pp.14-27, 1996-11

著者

松原 洋 小澤 正直 吉信 康夫 築地 立家 佐藤 潤也 井原 俊輔 三井 斌友

出版者

名古屋大学

雑誌

基盤研究(C)

巻号頁・発行日

1999

---

計算可能性と多項式時間計算可能性の分野は、集合論、帰納的関数論、計算量理論、学習理論、確率モデル論、量子計算量理論等と密接に関係しており、本研究の研究実績も多岐にわたる.以下はそれぞれの分野における成果のいくつかを報告する.詰め将棋の計算量:8×8の桝目をn×nに拡張し、コマの個数をo(n)にして詰め将棋を作成したとき、一般化詰め将棋問題はEXPTIME完全であることを示した.これにより、一般化将棋もEXPTIME完全であることになる.確率モデル:一様ランダムに生成される回路の出力端子の個数の分布を決定した.学習1:負例のみからなるサンプルと無矛盾なo(logn)長の単調単項式を提出する問題の計算複雑さは、AND-OR-AND型の3段並列回路でo((logn)^2)個の入力変数をもつものの充足回発見問題と対数領域還元について同等であることをしめした.学習2:包除の原理を応用してDNF式を2^<o(√n)>時間で学習するアルゴリズムをえた.さらに、これ以上高速には学習できないことを頑健学習モデルの上で証明した.学習3:o(logn)個の変数に依存する一般の関数について、その関係変数を高速に発見する3種類のアルゴリズムを提案した.吉信はApproachability Propertyという無限組合せ論の命題と、ある条件を満たしたゲームの必勝法の存在のextendabilityという性質が同値だということを証明した.松原はS.Shelahとの共同研究でλがstrong limit singular cardinalであれば、NS_<kλ>はprecipitousにはなれないことを証明した.さらにこの結果を使って、Menasの予想がλがstrong limit singular cardinalの場合に成立することを証明した.