2000 character limit reached
Complexity of majorants
Published 6 Apr 2020 in math.LO, cs.IT, and math.IT | (2004.02844v2)
Abstract: 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 we replace "everywhere" by "for all sufficiently large inputs", the answer is $n+O(1)$.
Paper Prompts
Sign up for free to create and run prompts on this paper using GPT-5.
Top Community Prompts
Collections
Sign up for free to add this paper to one or more collections.
