2005 | OriginalPaper | Chapter
Recursion Theoretic Operators for Function Complexity Classes
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
FPSPACE
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
FPSPACE
by using these classes and operators. Finally, we define a new notion of completeness for
FPSPACE
and show a
FPSPACE
-complete function.