Anti-complex sets and reducibilities with tiny use

DOI10.2178/JSL.7804170MaRDI QIDQ5407055zbMATH OpenOpenAlexFDO

Authors Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan, Guohua Wu

Publication date 4 April 2014

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.0304, https://projecteuclid.org/euclid.jsl/1388954008, http://hdl.handle.net/10220/19366

zbMATH Keywords

Kolmogorov complexityprefix-free machinesr.e. traceable degreesreducibility with tiny useSchnorr trivial setsweak truth-table degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: In contrast with the notion of complexity, a set $A$ is called anti-complex if the Kolmogorov complexity of the initial segments of $A$ chosen by a recursive function is always bounded by the identity function. We show that, as for complexity, the natural arena for examining anti-complexity is the weak-truth table degrees. In this context, we show the equivalence of anti-complexity and other lowness notions such as r.e. traceability or being weak truth-table reducible to a Schnorr trivial set. A set $A$ is anti-complex if and only if it is reducible to another set $B$ with emph{tiny use}, whereby we mean that the use function for reducing $A$ to $B$ can be made to grow arbitrarily slowly, as gauged by unbounded nondecreasing recursive functions. This notion of reducibility is then studied in its own right, and we also investigate its range and the range of its uniform counterpart.

Recommendations

• Schnorr trivial sets and truth-table reducibility
• About Segment Complexity of Turing Reductions
• Sub-Turing reducibilities of restricted complexity
• Lowness properties and randomness

Cited in

(8)

• Reductions between types of numberings
• Unified characterizations of lowness properties via Kolmogorov complexity
• On effectively closed sets of effective strong measure zero
• Strong jump-traceability
• A hierarchy of computably enumerable degrees
• About Segment Complexity of Turing Reductions
• Randomness for computable measures and initial segment complexity
• Kobayashi compressibility

This page was built for publication: Anti-complex sets and reducibilities with tiny use

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