Superposition Problem of Continuous Functions. A Communication Approach

F. M. Ablayev ; S. G. Ablaeva

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 150 (2008) no. 1, pp. 5-18

Résumé

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$ 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.

Détail

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