Anti-complex sets and reducibilities with tiny use

• Main Authors: Franklin, Johanna N. Y., Greenberg, Noam, Stephan, Frank, Wu, Guohua
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2014
• 主題: DRNTU::Science::Physics
• 在線閱讀: https://hdl.handle.net/10356/103705; http://hdl.handle.net/10220/19366
• 機構: 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-...