Complexity of majorants - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2020

Complexity of majorants

Alexander Shen


The minimal Kolmogorov complexity of a total computable function that exceeds everywhere all total computable functions of complexity at most n, is 2 n+O(1). If "everywhere" is replaced by "for all sufficiently large inputs", the answer is n + O(1). The notion of Kolmogorov complexity of computable function was first considered by Schnorr [1]. The (plain) complexity of a computable function is the minimal length of a program that computes this function. As usual, we require that the programming language is optimal, i.e., leads to a minimal complexity up to O(1). One can also define the plain complexity of a function as the minimal complexity of its programs. In this case we may use any Gödel numbering of programs. Consider all total computable functions that have complexity at most n. Alexey Milovanov asked the following question: What is a minimal complexity of a total computable function that exceeds all of them?
Fichier principal
Vignette du fichier
2004.02844.pdf (71.36 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03059689 , version 1 (12-12-2020)



  • HAL Id : lirmm-03059689 , version 1


Alexander Shen. Complexity of majorants. 2020. ⟨lirmm-03059689⟩
32 View
15 Download


Gmail Mastodon Facebook X LinkedIn More