Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees

DOI10.1016/S0168-0072(01)00090-2zbMath1054.03031OpenAlexW2077718801MaRDI QIDQ1612486

Benjamin Schaeffer

Publication date: 22 August 2002

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(01)00090-2

zbMATH Keywords

generic setsdegrees of unsolvability\(\Delta_{0}^{2}\) degreesAbstract Complexity TheoryYu. L. Ershov's difference hierarchy of sets

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Cites Work

• Computable models of theories with few models
• Δ 2 0 -Mengen
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Dichotomy of the Recursively Enumerable Sets
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Computational Complexity and the Existence of Complexity Gaps
• ∏ 0 1 Classes and Degrees of Theories
• Computability and Recursion
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees