Anti-complex sets and reducibilities with tiny use

Details Anti-complex sets and reducibilities with tiny use Anti-complex sets and reducibilities with tiny use

2011-10-03

arxiv.org/abs/1110.0304v1

Mathematics

Logic

20

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Anti-complex sets and reducibilities with tiny use does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Anti-complex sets and reducibilities with tiny use, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Anti-complex sets and reducibilities with tiny use will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-270803