Recursion Theoretic Operators for Function Complexity Classes

スポンサーリンク

概要

• 論文の詳細を見る

• We characterize the gap between time and space complexity of functions by operators and completeness. First, we introduce a new notion of operators for function complexity classes based on recursive function theory and construct an operator which generates FPS PACE from FP. Then, we introduce new function classes composed of functions whose output lengths are bounded by the input length plus some constant. We characterize FP and FPS PACE by using these classes and operators. Finally, we define a new notion of completeness for FPS PACE and show a FPS PACE-complete function.

• （社）電子情報通信学会の論文
• 2008-04-01

著者

• Ueno Kenya

  Department Of Computer Science Graduate School Of Information Science And Technology The University

関連論文

• Recursion Theoretic Operators for Function Complexity Classes

スポンサーリンク