Anti-Complex Sets and Reducibilities with Tiny Use
Anti-Complex Sets and Reducibilities with Tiny Use
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 …