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财年冠状病毒大流行的重大影响，决定该计划的大部分内容将在2020财年实施，但取得了以下主要成果。 (1) 在实数紧集的表示中，基于有限覆盖的表示和有界闭集的表示在某种意义上可以转化为可计算项，但使用多项式时间等计算资源也可以完成同样的事情。人们发现，即使在有限的情况下，它在某些条件下也成立（海涅-博雷尔定理的计算复杂性）。 (2) 在无理数的表达式中，我们通过有限的计算量比较了卡尔玛初等函数范围内的可计算等价和近似、连分数、追踪等，发现前人研究中预测的不可译性我们得到了几个结果，包括证明这一点。（3）最近研究中发现的关于二阶完整序列（由多项式系数的三项递推公式描述的实数序列）所表现出的渐近周期行为的分类定理及其可计算性被扩展到更一般的情况。我们已经在日本和国外的研究会议上对上述结果进行了初步介绍，但我们的目标是进一步研究它们，并在明年以论文形式发表。此外，Park等人去年关于如何处理非确定性（非确定性距离完成）的研究成果已于2020年发表，该结果对于方便地使用从近似序列获得的构造性实数至关重要。在 NASA 形式方法研讨会 (NFM) 上。在令和4年夏天举办的“组合优化研讨会”上，我们主要向邻近领域的年轻人介绍了可计算分析领域，包括这方面的研究。