Abstract complexity theory and the Δ20 degrees

AbstractWe show how Abstract Complexity Theory is related to the degrees of unsolvability and develop machinery by which computability theoretic hierarchies with a complexity theoretic flavor can be defined and investigated. This machinery is used to prove results both on hierarchies of Δ20 sets and hierarchies of Δ20 degrees. We prove a near-optimal lower bound on the effectivity of the Low Basis Theorem and a result showing that array computable c.e. degrees are, in some sense, the simplest possible Δ20 degrees. We also examine the growth rates of iterates of mK. Finally, we indicate how complexity theory can be used to analyze notions of genericity intermediate between 1-genericity and 2-genericity, and produce a hierarchy of such notions