関数の時間、領域計算量について

スポンサーリンク

概要

論文の詳細を見る
計算可能な関数のクラスと同様に、FP、FPSPACEといった多くの関数計算量クラスは帰納理論的に特徴付けられることが知られている。これらの結果をもとに、一般の関数計算量クラスに対する演算子という概念を導入する。これにより、時間、領域制約関数計算量クラス間の関係を特徴付ける演算子を構成する。また、出力長が入力長の高々定数しか長くならないような関数のクラスを導入し、これらのクラスと演算子を用いてFP、FPSPACEを特徴付ける。さらに、FPSPACE完全性の概念を定義しFPSPACE完全な関数を示す。
社団法人電子情報通信学会の論文
2005-04-11

著者

上野賢哉
東京大学大学院情報理工学系研究科コンピュータ科学専攻

関連論文

スポンサーリンク