Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Regular Section -- Papers -- Computation and Computational Models |
Recursion Theoretic Operators for Function Complexity Classes*
1 The author is with the Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, 113–8656 Japan.E-mail: kenya{at}is.s.u-tokyo.ac.jp
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 FP SPACE 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 FP SPACE by using these classes and operators. Finally, we define a new notion of completeness for FP SPACE and show a FP SPACE-complete function.
Key Words: recursive function theory, function complexity classes, operators for complexity classes
Manuscript received August 27, 2007. Manuscript revised November 30, 2007.
* This paper was presented at The 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), Sanya, Hainan, China, December, 2005.
Reference
[1] J. Balcázar, J. Díaz, and J. Gabarró, Structural Complexity I, 2nd ed., Springer, 1994. [2] S. Bellantoni and S. Cook, "A new recursion-theoretic characterization of the polytime functions," Computational Complexity, vol.2, no.2, pp.97–110, 1992. [3] P. Clote and E. Kranakis, Boolean Functions and Computation Models, Springer, 2002. [4] A. Cobham, "The intrinsic computational difficulty of functions," Proc. 1964 Congress for Logic, Methodology, and the Philosophy of Science, pp.24–30, North-Holland, 1964. [5] A. Grzegorczyk, "Some classes of recursive functions," Rozprawy Mathematyczne, vol.4, pp.xx–xx, 1953. [6] M. Hofmann, "Type systems for polynomial-time computation," Technical Report, University of Edinburgh, 1998. [7] J.E. Hopcroft, W. Paul, and L.G. Valiant, "On time versus space," J. ACM, vol.24, pp.332–337, 1977. [8] S.C. Kleene, "General recursive functions of natural numbers," Mathematical Annals, vol.112, pp.727–742, 1936. [9] R.E. Ladner, "Polynomial space counting problems," SIAM J. Comput., vol.18, no.6, pp.1087–1097, Dec. 1989. [10] M. Ogiwara and L.A. Hemachandra, "A complexity theory for feasible closure properties," Structure in Complexity Theory Conference, pp.16–29, 1991. [11] R.W. Ritchie, "Classes of predictably computable functions," Transactions of the American Mathematical Society, vol.106, pp.139–173, 1963. [12] H.E. Rose, Subrecursion: Functions and Hierarchies, Claredon Press, 1984. [13] A.L. Selman, "Much ado about functions," Proc. Eleventh Annual IEEE Conference on Computational Complexity, pp.198–212, 1996. [14] A.L. Selman, M.-R. Xu, and R.V. Book, "Positive relativizations of complexity classes," SIAM J. Comput., vol.12, no.3, pp.565–579, Aug. 1983. [15] D.B. Thompson, "Subrecursiveness: Machine-independent notions of computability in restricted time and storage," Mathematical Systems Theory, vol.6, no.1, pp.3–15, 1972. [16] S. Toda, "PP is as hard as the polynomial-time hierarchy," SIAM J. Comput., vol.20, no.5, pp.865–877, Oct. 1991. [17] H. Vollmer and K. Wagner, "Classes of counting functions and complexity theoretic operators," Technical Report, Universitat Wurzburg, 1991. [18] S. Zachos and A. Pagourtzis, "Combinatory complexity: Operators on complexity classes," Proc. Panhellenic Logic Symposium, 2003.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by UENO, K.
Social Bookmarking
What's this?