Complexity of majorants - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Pré-Publication, Document De Travail Année : 2020

Complexity of majorants

Alexander Shen

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Licence

Identifiants

  • HAL Id : lirmm-03059689 , version 1

Citer

Alexander Shen. Complexity of majorants. 2020. ⟨lirmm-03059689⟩
42 Consultations
22 Téléchargements

Partager

More