The recursion-theoretic structure of complexity classes

AbstractWe prove easy recursion-theoretic results which have as corollaries generalizations of existing diagonalization theorems on complexity classes: roughly speaking, almost no ‘reasonable’ (time, space or even abstract) complexity class can be expressed as the (non-trivial) union of two recursively presentable classes which are closed under finite variations (e.g. unless NP = P, NP ≠ P ∪ {NP-complete languages}); and, consequently, the non-trivial complement of one complexity class in another (e.g. (NPP), provided NP ≠ P) is almost never recursively presentable