令和4年度 組合せ最適化セミナー
計算を理解するための，例えばチューリング機械に基づく枠組は，すべての処理を有限的な基本単位に分解して考えるという離散的なものである．一方で実世界の課題には，何らかの量や図形に関する情報という形で実数を含む問題と考えるのが自然なものも多い．そのような問題の計算可能性や計算量を数学的に正確な形で扱うには，計算理論の考え方をうまく拡張する必要がある．計算可能の枠内で解析学的対象を扱う分野なので，計算可能解析学（computable analysis）などと呼ばれている．
計算可能性理論では早くから実数や実函数も興味の対象となってはおり，これを精密化して時間等の資源を限った計算量を考えることも1980年代の葛とフリードマンに遡ることができるが，理論の整備が進んで様々な対象を扱えるようになってきたのは比較的最近である．組合せ的な問題の困難さを理解する尺度として確立した，多項式時間Pをはじめとする計算量級や，それらの関係に関する理論を，実数など連続量の絡む問題の複雑さ理解に応用するのである．本講義ではこの分野の考え方の枠組や典型的な結果について紹介する．