Degrees of Monotone Complexity

Journal of Symbolic Logic 71 (4):1327 - 1341 (2006)
Levin and Schnorr (independently) introduced the monotone complexity, Km(α), of a binary string α. We use monotone complexity to define the relative complexity (or relative randomness) of reals. We define a partial ordering ≤Km on 2ω by α ≤Km β iff there is a constant c such that Km(α ↾ n) ≤ Km(β ↾ n) + c for all n. The monotone degree of α is the set of all β such that α ≤Km β and β ≤Km α. We show the monotone degrees contain an antichain of size 2N0, a countable dense linear ordering (of degrees of cardinality 2N0), and a minimal pair. Downey, Hirschfeldt, LaForte, Nies and others have studied a similar structure, the K -degrees, where K is the prefix-free Kolmogorov complexity. A minimal pair of K -degrees was constructed by Csima and Montalbán. Of particular interest are the noncomputable trivial reals, first constructed by Solovay. We define a real to be (Km, K)-trivial if for some constant c, Km(α ↾ n) ≤ K(n)+c for all n. It is not known whether there is a Km-minimal real, but we show that any such real must be (Km, K)-trivial. Finally, we consider the monotone degrees of the computably enumerable (c.e.) and strongly computably enumerable (s.c.e.) reals. We show there is no minimal c.e. monotone degree and that Solovay reducibility does not imply monotone reducibility on the c.e. reals. We also show the s.c.e. monotone degrees contain an infinite antichain and a countable dense linear ordering
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1164060458
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 24,479
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

Add more references

Citations of this work BETA
Adam R. Day (2009). On the Computational Power of Random Strings. Annals of Pure and Applied Logic 160 (2):214-228.

Add more citations

Similar books and articles
Rodney G. Downey & Evan J. Griffiths (2004). Schnorr Randomness. Journal of Symbolic Logic 69 (2):533 - 554.
Theodore A. Slaman (1986). On the Kleene Degrees of Π11 Sets. Journal of Symbolic Logic 51 (2):352 - 359.
Philip Welch (1987). Minimality in the ▵13-Degrees. Journal of Symbolic Logic 52 (4):908 - 915.

Monthly downloads

Added to index


Total downloads

11 ( #381,718 of 1,925,764 )

Recent downloads (6 months)

2 ( #308,517 of 1,925,764 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.