On the complexity of approximate realization of some classical functions (Q1920136)

A. N. Kolmogorov has pointed out 1963 that the inverse theorems of approximation theory are not valid for the so-called bit complexity, because low complexity of a function does not imply its high smoothness. In this interesting paper, the author estimates the complexity of approximate realization for the nowhere differentiable functions of van der Waerden and Weierstrass, for the Peano mapping of \([0,1]\) onto \([0,1]^2\), and for the Cantor ladder. These functions are calculated by means of circuits constructed either from the basis \(\{x\pm y, xy, x/y, 1\}\) or from a basis of finitely many arithmetic operations. The author has shown that these functions can be realized by simple circuits whose complexity and depth are polynomially equivalent. Further, the complexity of formulas realizing these functions is exponentially large in comparison with the complexity of the minimal circuits. In other words, these functions are easily computable, but their computation cannot essentially accelerate by converting to parallel programs.