帰納的関数論の計算量問題への応用

本研究により本年度になされた結果の主なものをあげる。(1)一般化されたKolmogorov complexityに関して、self P-printableでない粗(sparse)な集合が存在することを示した。しかもそのような集合は連続体の濃度あることを示した(今田、篠田)。(2)集合論のブール値モデル内の超構造から超準宇宙を構成する方法を確立した。これにより、強制法が利用可能な超準解析学の新しい枠組みが得られる。その応用として,一様非完備な実数体のブール超巾を構成することに成功した(小澤)。(3)計算量クラスの分離問題に関して、Ajtaiの方法を分析して非標準モデル上のBool値モデルの理論作りを上げ、それを用いてIΣ_0+Pigeon Hole PrincipleからCountが導かれないことを示した(安本)。(4)過渡的な加法過程を強過渡的、弱過渡的へ分類する判定条件を、その対数特性関数の性質によって与えた。さらに,再帰的,過渡的のSpitzer型の判定条件の対応物は得ることができないということを示した。この判定条件を用いて、5次元以上の非退化の加法過程が必ず強過渡的であることなどを示した(佐藤)。(5)通信路容量,相互情報量,および2乗平均誤差の間に成り立ついくつかの不等式を証明した(井原)。これらの不等式は情報理論において基本的な役割を果たすことが期待される。(6)確率過程の応用として、光合成において重要な意味を持つ金属錯体の分子進化論を考察し、遺伝子の中立説的な結論を導いた(森本)。

本研究により本年度になされた結果の主なものをあげる。(1)一般化されたKolmogorov complexityに関して、self P-printableでない粗(sparse)な集合が存在することを示した。しかもそのような集合は連続体の濃度あることを示した(今田、篠田)。(2)集合論のブール値モデル内の超構造から超準宇宙を構成する方法を確立した。これにより、強制法が利用可能な超準解析学の新しい枠組みが得られる。その応用として,一様非完備な実数体のブール超巾を構成することに成功した(小澤)。(3)計算量クラスの分離問題に関して、Ajtaiの方法を分析して非標準モデル上のBool値モデルの理論作りを上げ、それを用いてIΣ_0+Pigeon Hole PrincipleからCountが導かれないことを示した(安本)。(4)過渡的な加法過程を強過渡的、弱過渡的へ分類する判定条件を、その対数特性関数の性質によって与えた。さらに,再帰的,過渡的のSpitzer型の判定条件の対応物は得ることができないということを示した。この判定条件を用いて、5次元以上の非退化の加法過程が必ず強過渡的であることなどを示した(佐藤)。(5)通信路容量,相互情報量,および2乗平均誤差の間に成り立ついくつかの不等式を証明した(井原)。これらの不等式は情報理論において基本的な役割を果たすことが期待される。(6)確率過程の応用として、光合成において重要な意味を持つ金属錯体の分子進化論を考察し、遺伝子の中立説的な結論を導いた(森本)。