Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/103705
Title: | Anti-complex sets and reducibilities with tiny use | Authors: | Franklin, Johanna N. Y. Greenberg, Noam Stephan, Frank Wu, Guohua |
Keywords: | DRNTU::Science::Physics | Issue Date: | 2013 | Source: | 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. | Series/Report no.: | The Journal of Symbolic Logic | 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. | URI: | https://hdl.handle.net/10356/103705 http://hdl.handle.net/10220/19366 |
DOI: | 10.2178/jsl/1067620177 | Schools: | School of Physical and Mathematical Sciences | Rights: | © 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. | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
anti-complex-sets.pdf | 225.03 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
50
3
Updated on Mar 26, 2024
Web of ScienceTM
Citations
50
3
Updated on Oct 30, 2023
Page view(s) 50
596
Updated on Mar 28, 2024
Download(s) 20
246
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.