Logical Approaches to Computational Barriers

Triviality and Minimality in the Degrees of Monotone Complexity

Speaker:
| William Calhoun |

Slot: |
Array, 11:40-12:00, col. 3 |

This work extends the author's article Degrees of Monotone Complexity (2006). Monotone complexity is a variant of Kolmogorov complexity that was introduced independently by Levin and Schnorr. Monotone complexity was used in the previous article to define the relative complexity (or randomness) of reals. Equivalence classes of reals under monotone complexity are the monotone degrees, similar to the K-degrees defined via prefix-free complexity. In this paper, the Km-trivial reals are defined and shown to be equivalent to the (Km,K)-trivial reals. A nondecreasing function is defined to be computably infinitesimal if it is dominated by every computable, nondecreasing, unbounded function. It is shown that if a real is Km-trivial then its monotone complexity is computably infinitesimal. If a Km-minimal real exists, it is Km-trivial. The operation \otimes, defined previously, horizontally stretches the complexity graph of a real \alpha by a strictly increasing computable function f. Here, \alpha is defined to be invariant under computable stretching if \alpha \otimes f is monotone equivalent to \alpha for any such f. It is shown that any Km-minimal real must be invariant under computable stretching.

websites: Arnold Beckmann | 2008-05-28 |