Recursive Properties of Abstract Complexity Classes

It is proven that complexity classes of abstract measures of complexity need not be recursively enumerable, However, the complement of each class is shown to be r.e. The results are extended to complexity classes determined by partial functions, and the properties of these classes are investigated. Properties of effective enumerations of complexity classes are studied. For each measure another measure with the same complexity classes is constructed such that almost every class admits an effective enumeration of efficient devices. Finally complexity classes are shown not to be closed under intersection.

Download this report (PDF)

Return to tech report index