Abstract complexity theory and the _2⁰ degrees

DOI10.1016/S0168-0072(01)00090-2zbMATH Open1054.03031OpenAlexW2077718801MaRDI QIDQ1612486FDOQ1612486

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Computational Complexity and the Existence of Complexity Gaps
• ∏ 0 1 Classes and Degrees of Theories
• Title not available (Why is that?)
• Computable models of theories with few models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Computability and Recursion
• Δ 2 0 -Mengen
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Dichotomy of the Recursively Enumerable Sets

Cited In (2)

• 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)