Abstract complexity theory and the Δ20 d
✍
Benjamin Schaeffer
📂
Article
📅
2002
🏛
Elsevier Science
🌐
English
⚖ 248 KB
We show how Abstract Complexity Theory is related to the degrees of unsolvability and develop machinery by which computability theoretic hierarchies with a complexity theoretic avor can be deÿned and investigated. This machinery is used to prove results both on hierarchies of 0 2 sets and hierarchie