Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T06:39:58.146Z Has data issue: false hasContentIssue false

Anti-Complex Sets and Reducibilities with Tiny Use

Published online by Cambridge University Press:  12 March 2014

Johanna N. Y. Franklin
Affiliation:
Department of Mathematics, 196 Auditorium Road, University of Connecticut, U-3009, Storrs, CT 06269-3009, USA, E-mail: johanna.franklin@uconn.edu
Noam Greenberg
Affiliation:
School of Mathematics, Statistics and Computer Science, Victoria University of Wellington, PO Box 600, Wellington 6140, New zealand, E-mail: greenberg@msor.vuw.ac.nz
Frank Stephan
Affiliation:
Department of Computer Science and Department of Mathematics, National University of Singapore, Singapore 117543, Republic of Singapore, E-mail: fstephan@comp.nus.edu.sg
Guohua Wu
Affiliation:
Department of Computer Science and Department of Mathematics, National University of Singapore, Singapore 117543, Republic of Singapore, E-mail: fstephan@comp.nus.edu.sg

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 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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable