\(\varepsilon\)-Entropy of compact sets in \(C\) and tabulation of continuous functions (Q1375025)

Let \(X\) and \(Y\) be compact metric spaces, let \(\omega\) be a modulus of continuity, and let \(F_\omega\) be a set of \(\omega\)-continuous functions \(X\to Y\). In the article under review, the author gives a condition on \(X\) that is equivalent to the statement that the \(\varepsilon\)-entropy of the space \(F_\omega\) asymptotically equals to \(O\bigl( 2^{H_X(\omega^{-1}(\varepsilon))}\bigr)\) as \(\varepsilon\to +0\). This result of the author generalizes some theorems of A. G. Vitushkin and A. F. Timan (see, for example, \textit{A. F. Timan} [Sov. Math., Dokl. 8, 1418-1420 (1967; Zbl 0172.07102)]). The proof proposed by the author of the article under review is based on some other ideas than the proofs by Vitushkin and Timan. In particular, these new ideas allow the author to deny the condition that \(X\) is connected. Besides, in the article under review, a method is proposed for \(\varepsilon\)-approximation of continuous and differentiable functions by sums of step functions or piecewise polynomial functions with minimal total complexity. In some sense, the method proposed by the author is similar to the process of expanding in a series with respect to the Walsh orthogonal system. To the best of reviewer's knowledge, such a method has never been employed in the algorithmic information theory. This part of the article generalizes results by \textit{E. A. Asarin} [Russ. Math. Surv. 39, No.3, 179-193 (1984; Zbl 0609.41021)].