Abstract complexity theory and the _2⁰ degrees

DOI10.1016/S0168-0072(01)00090-2MaRDI QIDQ1612486zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 1795232
• On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
• Every \({\Delta}^0_2\)-set is natural, up to Turing equivalence
• Bounded query classes and the difference hierarchy
• Mathematical Foundations of Computer Science 2003
• On the hierarchies of Δ₂⁰-real numbers
• scientific article; zbMATH DE number 5381050
• Elementary differences between the degrees of unsolvability and degrees of compressibility
• Classifying model-theoretic properties
• On classes of computable functions

Cites work

• scientific article; zbMATH DE number 4172959 (Why is no real title available?)
• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3732038 (Why is no real title available?)
• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 841084 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3342830 (Why is no real title available?)
• scientific article; zbMATH DE number 3342831 (Why is no real title available?)
• A Dichotomy of the Recursively Enumerable Sets
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Computability and Recursion
• Computable models of theories with few models
• Computational Complexity and the Existence of Complexity Gaps
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Δ 2 0 -Mengen
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(3)

• Maximality and collapse in the hierarchy of \(\alpha\)-c.a. degrees
• Calibrating the complexity of \(\Delta_2^0\) sets via their changes
• \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1612486)