Computational complexity of continuous systems

连续系统的计算复杂性

基本信息

批准号：
18H03203
负责人：
河村彰星
金额：
$ 10.9万
依托单位：
Kyoto University (2019-2022)Kyushu University (2018)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2018
资助国家：
日本
起止时间：
2018-04-01 至 2023-03-31
项目状态：
已结题

项目摘要

令和3年度中にコロナ禍により大きな影響を受け、計画の多くの部分を令和4年度中に実施することとなったが、主に以下の成果が得られた。（1）実数のコンパクト集合の表現のうち有限被覆に基づくものと有界閉集合としてのものとの間は或る意味で互いに計算可能に翻訳できるが、同様のことが多項式時間など計算資源を限った場合にも一定の条件下で成立つことが判った（ハイネ・ボレルの定理の計算量）。（2）無理数の表現のうち計算可能には等価な和近似、連分数、追跡などについて、計算量を限ったカルマール初等的函数の範囲で比較し、先行研究で予想されていた翻訳不可能性を証明するなど幾つかの結果を得た。（3）2階ホロノミック列（多項式を係数とする3項間漸化式で記述される実数列）が呈する漸近的な周期挙動やその計算可能性について、最近の研究で発見されていた分類定理を、より一般の場合に拡張した。以上の結果については国内外の研究集会で予備的な発表を行ったが、引続き翌年度以降に更なる検討を加えて論文化を目指す。また、近似列から得る構成的実数を便利に使うために不可欠な非決定性の扱い方（非決定的な距離完備化）に関する研究員の朴氏らによる前年度からの成果は、令和4年度に入ってからNASA形式手法シンポジウム（NFM）で発表された。令和4年夏に行われた「組合せ最適化セミナー」で、主に隣接分野の若手に向け、本課題の研究を含む計算可能解析分野の入門的解説を行った。

在2021财政年度期间，冠状病毒大流行受到严重影响，该计划的许多部分将在2022财政年度实施，但主要取得了以下结果。（1）可以以某种方式翻译基于有限涂层的真实数字集的表达式，这些表达式基于有限的涂层，可以将它们彼此进行计算，但已经发现，即使在多项式时间（例如多项式时间）是有限的计算资源，Heine-Borel's theorem theorem的计算资源也是如此。（2）我们比较了在非理性数字中，非理性数字之间可计算在内的总和近似值，连续分数和跟踪，在非理性数字的表达中，在一系列具有有限的计算复杂性的Kalmaard基本功能上，并获得了多个结果，包括证明先前研究中预测的植物学潜力。（3）在最近的研究中发现的分类定理已扩展到更一般的情况，就二阶载体序列的渐近周期性行为和计算潜力（以多项式为系数为系数的三元复发方程中描述的真实序列）。上述结果是在国内和国际上的研究会议上提出的，但他们将继续专注于从次年开始的进一步考虑，以创建一种讨论文化。此外，研究人员公园和其他人在如何处理非确定性（非确定性距离的完成）上的结果，这对于在NASA形式上的序列中提供的方便使用，这对于自NASA形式上的序列中获得了本构型实数，自2022年以来，在2022年开始就介绍了“ Combodized Onsportiation in 202”。计算分析领域，主要针对相邻领域的年轻人，包括对此主题的研究。