Anti-complex sets and reducibilities with tiny use

• المؤلفون الرئيسيون: Franklin, Johanna N. Y., Greenberg, Noam, Stephan, Frank, Wu, Guohua
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: English
• منشور في: 2014
• الموضوعات: DRNTU::Science::Physics
• الوصول للمادة أونلاين: https://hdl.handle.net/10356/103705; http://hdl.handle.net/10220/19366

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