Article collection "Mathematical Problems of Cybernetics" №5, Moscow, 1994

Authors:Gashkov S.B.

On the complexity of continuous functions approximate implementation by circuits and formulas in the polynomial and some other bases

Abstract:

The present article investigates the complexity of continuous functions approximate implementation by circuits and formulas in finite continuous bases: the polynomial, the piecewise polynomial and the bases with a continuum of constants. The formulas are here understood as circuits without branching of elements' outputs (while the circuit inputs may branch). For the bases above we obtain estimates of the ԑ-approximation complexity.

Keywords:

continuous real-valued functions of several variables, uniform metric, uniform approximation, modulus of continuity of k-th order on a given variable, Holder condition, Kolmogorov ԑ-entropy, schemes and formulas in continuous bases, non-branching programs, complexity of continuous functions implementation by schemes and formulas