On Kolmogorov's Superposition and Boolean Functions

The paper overviews results dealing with the approximation capabilities of neural networks, as well as bounds on the size of threshold gate circuits. Based on an explicit numerical (i.e., constructive) algorithm for Kolmogorov's superpositions we show that for obtaining minimum size neural networks for implementing any Boolean function, the activation function of the neurons is the identity function. Since classical AND-OR implementations, as well as threshold gate implementations which require exponential size (in the worst case), it follows that size-optimal solutions for implementing arbitrary Boolean functions require analog circuitry. Conclusions and several comments on the required precision are presented.