Anti-complex sets and reducibilities with tiny use

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

Full description

Saved in:
Bibliographic Details
Main Authors: Franklin, Johanna N. Y., Greenberg, Noam, Stephan, Frank, Wu, Guohua
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2014
Subjects:
Online Access:https://hdl.handle.net/10356/103705
http://hdl.handle.net/10220/19366
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-103705
record_format dspace
spelling sg-ntu-dr.10356-1037052023-02-28T19:29:29Z Anti-complex sets and reducibilities with tiny use Franklin, Johanna N. Y. Greenberg, Noam Stephan, Frank Wu, Guohua School of Physical and Mathematical Sciences DRNTU::Science::Physics 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. Published version 2014-05-19T02:49:09Z 2019-12-06T21:18:25Z 2014-05-19T02:49:09Z 2019-12-06T21:18:25Z 2013 2013 Journal Article Franklin, J. N. Y., Greenberg, N., Stephan, F., Wu, G. (2003). Anti-complex sets and reducibilities with tiny use. The Journal of Symbolic Logic, 68(04), 1145-1162. https://hdl.handle.net/10356/103705 http://hdl.handle.net/10220/19366 10.2178/jsl/1067620177 177266 en The Journal of Symbolic Logic © 2013 Association for Symbolic Logic. This paper was published in The Journal of Symbolic Logic and is made available as an electronic reprint (preprint) with permission of Association for Symbolic Logic. The paper can be found at the following official DOI: [http://dx.doi.org/10.2178/jsl/1067620177].  One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law. application/pdf
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic DRNTU::Science::Physics
spellingShingle DRNTU::Science::Physics
Franklin, Johanna N. Y.
Greenberg, Noam
Stephan, Frank
Wu, Guohua
Anti-complex sets and reducibilities with tiny use
description 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.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Franklin, Johanna N. Y.
Greenberg, Noam
Stephan, Frank
Wu, Guohua
format Article
author Franklin, Johanna N. Y.
Greenberg, Noam
Stephan, Frank
Wu, Guohua
author_sort Franklin, Johanna N. Y.
title Anti-complex sets and reducibilities with tiny use
title_short Anti-complex sets and reducibilities with tiny use
title_full Anti-complex sets and reducibilities with tiny use
title_fullStr Anti-complex sets and reducibilities with tiny use
title_full_unstemmed Anti-complex sets and reducibilities with tiny use
title_sort anti-complex sets and reducibilities with tiny use
publishDate 2014
url https://hdl.handle.net/10356/103705
http://hdl.handle.net/10220/19366
_version_ 1759858065288462336