Anti-complex sets and reducibilities with tiny use. (English) Zbl 1307.03025

In literature, there are several notions trying to capture, from a computational point of view, the low information content of a set of natural numbers. Along this line, the authors give a new contribution by defining the concept of an anti-complex set, in contrast with the concept of a complex set introduced in [B. Kjos-Hanssen et al., Trans. Am. Math. Soc. 363, No. 10, 5465–5480 (2011; Zbl 1236.03032)]. A set \(A\) of natural numbers is anti-complex if for every order function \(f\) holds that \(C(A\upharpoonright f(n))\leq n\), where \(C(\cdot)\) is the plain Kolmogorov complexity and \(A\upharpoonright f(n)\) denotes the binary string \(A(0)A(1)\cdots A(f(n)-1)\). An order function is a recursive nondecreasing unbounded function. In the first part, the authors characterize anti-complex sets. Precisely, they give the following characterization: given a set \(A\), the following four properties are equivalent.

1) There is a set \(B\) such that \(A\leq_{\mathrm{T(tu)}}B\),

2) \(A\) is anti-complex,

3) deg\(_{\mathrm{wtt}}(A)\) is r.e. traceable,

4) \(A\) is weak truth-table reducible to a Schnorr trivial set.

In 1) \(\leq_{\mathrm{T(tu)}}\) denotes the nonreflexive binary relation called “Turing reducibility with tiny use” previously used in [N. Greenberg and A. Nies, J. Symb. Log. 76, No. 1, 289–312 (2011; Zbl 1221.03036)], and defined as follows: \(A \leq_{\mathrm{T(tu)}} B\) if for every order function \(h\) there is an oracle Turing machine \(M\) such that \(A=L(M^B)\) and the use function of \(M^B\) is bounded by \(h\).
In the second part of the paper, the distribution of the anti-complex sets in the Turing degrees is studied. It is shown that there are Turing degrees containing only anti-complex sets, namely: a Turing degree \({\mathbf a}\) contains only anti-complex sets if and only if \({\mathbf a}\) is r.e. traceable. Also, the existence of Turing degrees without anti-complex sets is analyzed. The authors first observe that the existence of such non r.e. Turing degrees directly follows from known results. Then, they prove the existence of r.e. Turing degrees without anti-complex sets. This extends the existence of r.e. Turing degrees without Schnorr trivial sets, which has been shown in [R. Downey et al., Math. Log. Q. 50, No. 6, 613–627 (2004; Zbl 1062.68064)]. The last section of the paper contains some studies on the ranges of the binary relations \(\leq_{\mathrm{T(tu)}}\) and \(\leq_{\mathrm{uT(tu)}}\), the latter the uniform version of the former.


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