Anti-complex sets and reducibilities with tiny use

• 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: DRNTU::Science::Physics
• Online Access: https://hdl.handle.net/10356/103705; http://hdl.handle.net/10220/19366
• Institution: Nanyang Technological University

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