Complexity classes of partial recursive functions (Preliminary Version)

ABSTRACT

This paper studies possible extensions of the concept of complexity class of recursive functions to partial recursive functions. Many of the well-known results for total complexity classes are shown to have corresponding, though not exactly identical, statements for partial classes. In particular, with two important exceptions, all results on the presentation and decision problems of membership for the two most reasonable definitions of partial classes are the same as for total classes. The exceptions concern presentations of the complements and maximum difficulty for decision problems of the more restricted form of partial classes. The last section of this paper shows that it is not possible to have an “Intersection Theorem”, corresponding to the Union Theorem of McCreight and Meyer, either for complexity classes or complexity index sets.

REFERENCES

• 1: Leonard Joel Bass, Hierarchies based on computational complexity and irregularities of classdetermining measured sets, 1970
• 2: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 3: Borodin, Allan B., "Computational complexity and the existance of complexity gaps," Proc. ACM Symp on Theory of Computing (May 1969), 67-78.
• 4: Constable, Robert L., "Extending and refining hierarchies of computable functions," Computer Sciences Tech. Rept. #25, Univ. of Wis. (June 1968).
• 5: David, Martin, Computability and Unsolvability, McGraw-Hill (1958), New York.
• 6: Dekker, J. C. E., and Myhill, J., "Some theorems on classes of recursively enumerable sets," Trans. AMS 89 (1958), 25-59.
• 7: L. H. Landweber , E. L. Robertson, Recursive properties of abstract complexity classes (Preliminary Version), Proceedings of the second annual ACM symposium on Theory of computing, p.31-36, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805146]
• 8: F. D. Lewis, Unsolvability considerations in computational complexity, Proceedings of the second annual ACM symposium on Theory of computing, p.22-30, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805145]
• 9: E. M. McCreight , A. R. Meyer, Classes of computable functions defined by bounds on computation: Preliminary Report, Proceedings of the first annual ACM symposium on Theory of computing, p.79-88, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805423]
• 10: Rice, H. G., "Classes of recursively enumerable sets and their decision problems," Trans. AMS 74 (1953), 358-366.
• 11: Rice, H. C., "On completely recursively enumerable classes and their key arrays," JSL 21, 3 (1956), 304-308.
• 12: Edward Lowell Robertson, III, Properties of complexity classes and sets in abstract computational complexity, 1970
• 13: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Decision problems

General Terms:
Theory