Recursive Properties of Abstract Complexity Classes
Landweber, L. H.
Robertson, E. L.
University of Wisconsin-Madison Department of Computer Sciences
MetadataShow full item record
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.