Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
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