Superposition Problem of Continuous Functions. A Communication Approach

F. M. Ablayev, S. G. Ablaeva

Kazan State University

Abstract: In function theory the superposition problem is the problem of representing a continuous function $f(x_1,\dots,x_k)$ in $k$ variables as a composition of “simpler” functions. This problem stems from Hilbert's thirteenth problem. In computer science, good formalization for the notion of function composition is a formula.
The article considers real-valued continuous functions in $k$ variables in the cube $[0,1]^k$ from the class $\mathcal H^k_{\omega_p}$ with a special modulus of continuity $\omega_p$ defined in the article. $\mathcal H^k_{\omega_p}$ is a superset of Lipschitz' class of functions. An explicit function $f\in\mathcal H^k_{\omega_p}$ is presented, 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 $\{x_1,\dots,x_k\}$ (different input gates can be associated with the same variable $x_i\in\{x_1,\dots,x_k\}$), on the first level of the formula, arbitrary $t$ variable functions from $\mathcal H^t_{\omega_p}$ for $t<k$ are allowed, while the second (output) level may compute any Lipschitz' function.
We apply communication complexity for constructing such a hard explicit function. Remarkably, one can show the existence of such a function using the “non constructive” proof method known in the function theory as Kolmogorov's entropy method.

Keywords: superposition problem of continuous functions, Lipschitz function, Dini function, discrete approximation of continuous functions, communication complexity.

UDC: 519.95+517.5

Received: 15.01.2008

Bibliographic databases:

•