About Segment Complexity of Turing Reductions
hierarchy of relationsjump inversionKolmogorov complexityoracle Turing machinesuse restrictions on Turing reducibility
Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Given a class \(\mathcal F\) of non-decreasing functions from the set of natural numbers to itself, let \(\leq_{\mathcal F}\) be the restriction of Turing reducibility defined by the class of oracle Turing machines which for some \(f\) in \(\mathcal F\) and for all inputs \(x\), query their oracle only on places less than or equal to \(f(x)\). After introducing the relations \(\leq_{\mathcal F}\), the author gives conditions on \(\mathcal F\) which are equivalent to \(\leq_{\mathcal F}\) being reflexive and transitive and he shows that the structure of the power set of the natural numbers under inclusion can be embedded into the inclusion structure of the relations \(\leq_{\mathcal F}\) with countable \(\mathcal F\). Next, the author introduces a hierarchy of relations where every level of the hierarchy contains relations \(\leq_{\mathcal F}\) such that \(\mathcal F\) can be defined from the relations contained in the previous levels. Furthermore, the author relates the Kolmogorov complexity of initial prefixes of sets \(A\) and \(B\) where \(A\) is Turing reducible to \(B\) with use bound~\(f\). Finally the author shows that for countable \(\mathcal F\), Friedberg's jump inversion theorem fails with Turing reducibility replaced by \(\leq_{\mathcal F}\).
- Query-monotonic Turing reductions
- 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000. La Sorbonne, Paris, France, July 23-31, 2000
- BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
- scientific article; zbMATH DE number 1747699 (Why is no real title available?)
- Program-size complexity of intial segments and domination reducibility
- scientific article; zbMATH DE number 1421075 (Why is no real title available?)
- Anti-complex sets and reducibilities with tiny use
This page was built for publication: About Segment Complexity of Turing Reductions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4704660)