Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
type: Item
instance of: scholarly article
title: Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
zbMATH Open document ID: 1054.03031
DOI: 10.1016/S0168-0072(01)00090-2
author: Benjamin Schaeffer
published in: Annals of Pure and Applied Logic
publication date: 2002-08-22T00:00:00Z
review text: Principal contributions to \(\Delta_{0}^{2}\) sets were made by \textit{J. W. Addison} [``The method of alternating chains'', in: The theory of models, Proc. 1963 Int. Symp., Berkeley, 1--16 (1965; Zbl 0199.01201)], \textit{Yu. L. Ershov} [``A hierarchy of sets. I'', Algebra Logic 7, 25--43 (1968), translation from Algebra Logika 7, No. 1, 47--74 (1968; Zbl 0216.00901); ``A hierarchy of sets. II'', Algebra Logic 7, 212--232 (1968), translation from Algebra Logika 7, No. 4, 15--47 (1968; Zbl 0216.00902); ``The hierarchy of \(\Delta_{0}^{2}\) sets'', in: Proc. 4th Int. Congr. Logic, Methodology and Philosophy of Science, Budapest, 1971, North-Holand, Amsterdam, 69--76 (1973)], and by \textit{R. Epstein, R. Haas} and \textit{R. Kramer} [``Hierarchies of sets and degrees below \(0'\)'', Lect. Notes Math. 859, 32--48 (1981; Zbl 0467.03046)]. In the paper under review the author investigates the complexity of \(\Delta_{0}^{2}\) sets (\(\Delta_{0}^{2}\) functions) examining their computable approximations in terms based on the Limit Lemma for \(\Delta _{0}^{2}\) functions. For any function \(g: N\rightarrow N\), a function \(f: N\rightarrow N\) is said to be \(g\)-c.e. if there exists a computable function \(h: N\times N\rightarrow N\) such that \(h(x,0)=0\), \(f(x)=\lim_{s}h(x,s)\) and for any input \(x\), the following inequality holds: \(\Delta_{h}(x)=\) cardinality \((\{s:h(x,s+1)\neq h(x,s))\leq g(x))\). The author illustrates how two well-known theorems concerning complexity theory -- A. Borodin's Gap Theorem [\textit{A. Borodin}, ``Computational complexity and the existence of complexity gaps'', J. Assoc. Comput. Mach. 19, 158--174 (1972); Corrigendum ibid. 19, 576 (1972; Zbl 0261.68024)] and M. Blum's Speed-up Theorem [\textit{M. Blum}, ``A machine-independent theory of the complexity of recursive functions'', J. Assoc. Comput. Mach. 14, 322--336 (1967; Zbl 0155.01503)] (as well as their \(K\)-relativized versions) -- can be elegantly reformulated in the \(\Delta_{…
reviewed by: Hrant B. Marandjian
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D55
zbMATH DE Number: 1787756
zbMATH Keywords: \(\Delta_{0}^{2}\) degrees
zbMATH Keywords: Abstract Complexity Theory
zbMATH Keywords: degrees of unsolvability
zbMATH Keywords: generic sets
zbMATH Keywords: Yu. L. Ershov's difference hierarchy of sets
MaRDI profile type: Publication
cites work: A Machine-Independent Theory of the Complexity of Recursive Functions
cites work: Computational Complexity and the Existence of Complexity Gaps
cites work: Δ 2 0 -Mengen
cites work: Q3197814
cites work: Q4863240
cites work: Q3919704
cites work: Q5619076
cites work: Q5619077
cites work: Degrees in Which the Recursive Sets are Uniformly Recursive
cites work: ∏ 0 1 Classes and Degrees of Theories
cites work: Computable models of theories with few models
cites work: Q3758821
cites work: Q4023358
cites work: Q4298260
cites work: A Dichotomy of the Recursively Enumerable Sets
cites work: Q5573961
cites work: Q3998976
cites work: Q3819052
cites work: Computability and Recursion
full work available at URL: s0168-0072(01)00090-2
OpenAlex ID: W2077718801
Recommended article: Q4552753
Recommended article: On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
Recommended article: Every $\Delta^0_2$ -Set Is Natural, Up to Turing Equivalence
Recommended article: Bounded query classes and the difference hierarchy
Recommended article: Mathematical Foundations of Computer Science 2003
Recommended article: On the hierarchies of Δ20-real numbers
Recommended article: Q3545563
Recommended article: Elementary differences between the degrees of unsolvability and degrees of compressibility
Recommended article: Classifying model-theoretic properties
Recommended article: On classes of computable functions
description: scientific article; zbMATH DE number 1787756