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

递归函数理论在计算复杂性问题中的应用

• 批准号: 07640298
• 负责人: 篠田 壽一
• 金额: $ 1.28万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-07640298/
• 关键词: 帰納的関数; 計算量; 超準解析; ブール値モデル; 確率過程

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

This study was conducted on the basis of the results of the study. (1)Generalization of Kolmogorov complexity, self P-printable, sparse, set existence The concentration of the compound is shown in Imada and Shinoda. (2)Set theory and structure of the superstructure in the universe This is because peremptory norms can be used to create new models of ultra-accurate analysis. A complete set of data structures is successfully constructed (Ozawa). (3)The method of calculating the separation of quantities is related to the analysis of Ajtai's method. The theoretical work of Bool's method on the non-standard model is described in detail. The method of calculating the separation of quantities is described in detail in the following paragraphs: IΣ_0+Pigeon Hole Principle (4)The transition additive process is classified into strong transition and weak transition. In addition, the transition of the Spitzer type of the determination conditions and the object is obtained in the first place. If this determination condition is used, a non-degenerate addition process above 5 dimensions will inevitably show a strong transition (Sato). (5)Communication channel capacity, mutual information amount, 2 average error between the formation of (Ihara). The inequality theory is based on the theory of information. (6)The important implications of determining the application of photosynthesis and molecular evolution of metal complexes are investigated, and the conclusions of neutral theory of inheritance are introduced (Morimoto).

项目成果

小澤 正直: "Scott incomplete Boolean ultrapowers of the real line." J.Symbolic-Logic. 60. 160-171 (1995)

Masanao Ozawa：“Scott 实数线的不完全布尔超幂。”J.Symbolic-Logic 60. 160-171 (1995)

井原俊輔: "Some inequalities for channel capacities,mutual informations and mean square errors." IEEE Trans.Information Theory. (近刊).

Shunsuke Ihara：“信道容量、互信息和均方误差的一些不等式。”IEEE Trans.Information Theory（即将出版）。

望月朝恵,篠田壽一: "A note on the functions which are not polynomial time computable from their graphs." Ann.Japan Assoc.Philos.Sci.近刊.

Asae Mochizuki、Juichi Shinoda：“关于不能从图表中计算多项式时间的函数的注释。”Ann.Japan Assoc.Philos.Sci.Forthcoming。

今田宏司、篠田壽一: "Kolmogorov complexity and P-printable sets" 数理解析研究所講究録. 930. 112-119 (1995)

Hiroshi Imada、Juichi Shinoda：“Kolmogorov 复杂度和 P-可打印集”数学科学研究所 Kokyuroku。930. 112-119 (1995)

森本宏: "A diffusion model for the evolution of metalloporphyrin." J.Math.Biology.(近刊).

Hiroshi Morimoto：“金属卟啉演化的扩散模型。”J.Math.Biology（即将出版）。