Affiliations: Departmnt of Theoretical Cybernetics, Kazan State University, Kazan, Russia. [email protected] | Department of Differential Equations, Kazan State University, Kazan, Russia
Note: [] Address for correspondence: Department of Theoretical Cybernetics, Kazan State University, Kremlevskaia str. 18, Kazan, 42008, Russia
Abstract: In function theory the superposition problem is known as the problem of representing a continuous function f(x1, … ,xk) in k variables as the composition of “simpler” functions. This problem stems from the Hilbert's thirteenth problem. In computer science good formalization for the notion of composition of functions is formula. In the paper we consider real-valued continuous functions in k variables in the cube [0,1]k from the class ℋkωp with ωp a special modulus of continuity (measure the smoothness of a function) defined in the paper. ℋkωp is a superset of Hölder class of functions. We present an explicit function f ∈ ℋkωp which is hard in the sense that it cannot be represented in the following way as a formula: zero level (input) gates associated with variables {x1, … ,xk} (different input gates can be associated with the same variable xi ∈ {x1, … ,xk}), on the first level of the formula, arbitrary number s ≥ 1 of t variable functions from ℋtωp for t < k are allowed, while the second (output) level may compute any s variable Hölder function. We apply communication complexity for constructing such hard explicit function. Notice that one can show the existence of such function using the “non constructive” proof method known in function theory as Kolmogorov's entropy method.
Keywords: Hilbert 13th problem, superposition of continuous functions, communication complexity
