The superposition (or composition) problem is a problem of representation of a function
f by a superposition of “simpler” (in a different meanings) set
Ω of functions. In terms of circuits theory this means a possibility of computing
f by a finite circuit with 1 fan-out gates
Ω of functions.
Using a discrete approximation and communication approach to this problem we present an explicit continuous function f from Deny class, that can not be represented by a superposition of a lower degree functions of the same class on the first
level of the superposition and arbitrary Lipshitz functions on the rest levels. The construction of the function f is based on particular Pointer function g (which belongs to the uniform AC0) with linear one-way communication complexity.
The research Supported partially Russia Fund for Basic Research under the grant 99-01-00163 and Fund “Russia Universities”
under the grant 04.01.52