Bienvenu, Laurent ;
Merkle, Wolfgang ;
Nies, Andre
Solovay functions and Ktriviality
Abstract
As part of his groundbreaking work on algorithmic randomness, Solovay demonstrated in the 1970s the remarkable fact that there are computable upper bounds of prefixfree Kolmogorov complexity $K$ that are tight on infinitely many values (up to an additive constant). Such computable upper bounds are called Solovay functions. Recent work of Bienvenu and Downey~[STACS 2009, LIPIcs 3, pp 147158] indicates that Solovay functions are deeply connected with central concepts of algorithmic randomness such as $Omega$ numbers, Ktriviality, and MartinLoef randomness.
In what follows, among other results we answer two open problems posed by Bienvenu and Downey about the definition of $K$triviality and about the GacsMillerYu characterization of MartinLoef randomness. The former defines a sequence A to be Ktrivial if K(An) <=^+ K(n), the latter asserts that a sequence A is MartinLoef random iff C(An) >=^+ nK(n). So both involve the noncomputable function K. As our main results we show that in both cases K(n) can be equivalently replaced by any Solovay function, and, what is more, that among all computable functions such a replacement is possible exactly for the Solovay functions. Moreover, similar statements hold for the larger class of all rightc.e. in place of the computable functions. These full characterizations, besides having significant theoretical interest on their own, will be useful as tools when working with Ktrivial and MartinLoef random sequences.
BibTeX  Entry
@InProceedings{bienvenu_et_al:LIPIcs:2011:3034,
author = {Laurent Bienvenu and Wolfgang Merkle and Andre Nies},
title = {{Solovay functions and Ktriviality}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {452463},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3034},
URN = {urn:nbn:de:0030drops30345},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.452},
annote = {Keywords: Algorithmic randomness, Kolmogorov complexity, Ktriviality}
}
Keywords: 

Algorithmic randomness, Kolmogorov complexity, Ktriviality 
Seminar: 

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Issue date: 

2011 
Date of publication: 

2011 