The computational power and complexity of discrete feedforward neural networks

Abstract

The number of binary functions that can be defined on a set of L vectors in R^N equals 2^L . For L>N the total number of threshold functions in N-dimensional space grows polynomially (2^N(N-1))while the total number of Boolean functions, definable on N binary inputs, growsexponentially ( 2^2^2), and as N increases a percentage of threshold functions in relation to the total number of Boolean functions - goes to zero. This means that for the realization of a majority of tasks a neural network must possess at least two or three layers. The examples of small computational problems are arithmetic functions, like multiplication, division, addition, exponentiation or comparison and sorting. This article analyses some aspects of two- and more than two layers of threshold and Boolean circuits (feedforward neural nets), connected with their computational power and node, edge and weight complexity.