𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Abstract complexity theory and the Δ20 degrees

✍ Scribed by Benjamin Schaeffer

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
248 KB
Volume
115
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

✦ Synopsis

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 hierarchies of 0 2 degrees. We prove a near-optimal lower bound on the e ectivity of the Low Basis Theorem and a result showing that array computable c.e. degrees are, in some sense, the simplest possible 0 2 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.

📜 SIMILAR VOLUMES

Complexity theory and the organization:
Complexity theory and the organization: beyond the metaphor
✍ Roger Lewin; Teresa Parker; Birute Regine 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 85 KB

Birute Regine is a visiting scholar at Wellesley College, MA, where she is researching a relational approach to the workplace. Roger Lewin, an Associate of the Peabody Museum, Harvard University, is author of Complexity: Life at the Edge of Chaos. Together, Regine and Lewin are writing a book titled

On the Relations Between Discrete and Co
On the Relations Between Discrete and Continuous Complexity Theory
✍ Klaus Meer 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 389 KB

A b s t r a c t . Relations between discrete and continuous complexity models are considered. The present paper is devoted to combine both models. In particular we analyze the 3-Satisfiability problem. The existence of fast decision procedures for this problem over the reds is examined based on cert