Kolmogorov Complexity and Solovay Functions

Simple item page
dc.creatorBienvenu, Laurent
dc.creatorDowney, Rod
dc.date2009-02-06
dc.date.accessioned2026-07-07T12:39:17Z
dc.date.available2026-07-07T12:39:17Z
dc.descriptionSolovay 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) <= f (x)+O(1) for all x and f (x) <= 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öf randomness and K-triviality.
dc.identifierhttps://arxiv.org/abs/0902.1041
dc.identifierhttp://arxiv.org/abs/0902.1041
dc.identifier26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 147-158
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/219052
dc.subjectComputational Complexity
dc.subjectInformation Theory
dc.subjectLogic
dc.titleKolmogorov Complexity and Solovay Functions
dc.typetext

Files

Collections

arXiv