LIPIcs.STACS.2009.1810.pdf
- Filesize: 182 kB
- 12 pages
Document
Kolmogorov Complexity and Solovay Functions
Authors
-
Part of:
Volume:
26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2009-02-19
Cite As Get BibTex
Laurent Bienvenu and Rod Downey. Kolmogorov Complexity and Solovay Functions. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 147-158, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.STACS.2009.1810
Abstract
Solovay (1975) proved that there exists a computable upper bound~$f$ of the prefix-free Kolmogorov complexity function~$K$ such that $f(x)=K(x)$ for infinitely many~$x$. In this paper, we consider the class of computable functions~$f$ such that $K(x) \leq f(x)+O(1)$ for all~$x$ and $f(x) \leq K(x)+O(1)$ for infinitely many~$x$, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality.
Subject Classification
Keywords
- Algorithmic randomness
- Kolmogorov complexity
- K-triviality
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads