Computational complexity of continuous systems

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

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