解析学における高階計算量
スポンサーリンク
概要
- 論文の詳細を見る
実数,実数集合,実函数など近似によってのみ表される対象を入出力とする問題について計算量を論ずるための枠組の拡張を提案する.これらの対象を符号化する名として従来しばしば用いられた無限文字列に代えて文字列から文字列への函数(の一部)を用いることにより,より多くの場合に計算量を扱うことができる.これは高階計算量の分野に倣って文字列函数に長さを導入することで,これを入力とする計算に費やす時間ないし空間が「多項式で抑えられる」ことを定義できることによる.これにより計算量級P, NP, PSPACE並びに適切な帰着の下でのNP完全.PSPACE完全の概念が,より一般の対象に拡張せられる.この枠組では機械による計算とその意味とが截然と分れているため,新たな対象へ応用するには符号化法を指定するだけでよい.本稿では実数,実数集合,実函数を入出力とする計算を考える.このうち実数集合と実函数は従来の無限文字列による方法では適切な符号化ができなかったため,これらを入出力とする演算の計算量を扱うのは本稿の方法が初である.例えば微分方程式を数値的に解くという課題は,実函数を実函数へ移す演算子とみるのが自然であるが,そのような演算子の計算量を述べる枠組が無かったために既存の結果では演算子の値である実函数の計算量が如何に高くなり得るかを述べるに留まっていた.本稿の方法によりこれを改良して演算子そのものが多項式空間完全であることを示すことができる.
- 2011-10-14