On the complexity of approximate realization of some classical functions
Nondifferentiability (nondifferentiable functions, points of nondifferentiability), discontinuous derivatives (26A27) Approximations and expansions (41A99) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
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.
- On the complexity of the approximate realization of certain classes of differentiable functions of one variable by formulas in certain continuous bases
- On the Kolmogorov complexity of functions of finite smoothness
- Complexity of functions: Some questions, conjectures, and results
- On the time complexity of partial real functions
- On the complexity of conversion between classic real number representations
- Feasible Real Functions and Arithmetic Circuits
- scientific article; zbMATH DE number 3903259 (Why is no real title available?)
- scientific article; zbMATH DE number 4023258 (Why is no real title available?)
- Complexity of approximating functions on real-life computers
- Peano curves and finite automata
This page was built for publication: On the complexity of approximate realization of some classical functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920136)
