On the Kolmogorov complexity of functions of finite smoothness (Q1080660)

The \(\epsilon\)-complexity, in the sense of Kolmogorov, of the class \(W^ r_ 1=\{f: [0,1]\to [-1,1],\) \(f^{(r-1)}\) is absolutely continuous, \(\int^{1}_{0}| f^{(r)}(x)| dx\leq 1\}\), \(r>1\), is asymptotically equal to \((1/\epsilon)^{1/r}/\log (1/\epsilon)\).