Complexity Classes of Partial Recursive Functions

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.

Download this report (PDF)

Return to tech report index