The enumerability and invariance of complexity classes

摘要

Several properties of complexity classes and sets associated with them are studied. An open problem, the enumerability of complexity classes, is settled by exhibition of a measure with some nonenumerable classes. Classes for natural measures are found to occupy the same isomorphism type; and a criterion for measures comes from this finding. General results about measures and unsolvability are presented and constraints are placed on complexity classes so that they possess identical properties.