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

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_{0}^{2}\) world. Moreover, the reformulations of these results, put forward by the author, give them a more general form than the original ones had. Two notions (among a wide variety of others) introduced by the author, and playing a significant role in the article, are the notion of \(\Delta_{0}^{2} \)-honest function \(f\) and the notion of \(f\)-approximable degree (in both cases keeping in mind that \(f\in\Delta_{0}^{2}\)). A series of hierarchy theorems on complexity bounds are proved or hinted at. The author shows the connection between a fragment of Yu. L. Ershov's difference hierarchy (restricted with \(\omega^{\alpha}\)-c.e. sets) and compositions of \(\Delta_{0}^{2}\) functions. In the last section the author obtains some results concerning a hierarchy of \(\Delta_{0}^{2}\) generic degrees. Unfortunately, it is impossible to give all the new concepts and results presented in the article within the limits of a review.