On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-in (Extended Abstract)

We consider the complexity of computing Boolean functions by analog circuits of bounded fan-in, i.e. by circuits of gates computing real-valued functions, either exactly or as a sign-representation. Sharp upper bounds are obtained for the complexity of the most &@cult n-variable function over certain bases (signrepresentation by arithmetic circuits and exact computation by piecewise linear circuits). Bounds are given for the computational power gained by adding discontinuous gate functions and nondeterminism. We also prove explicit nonlinear lower bounds for the formula size of analog circuits over bases containing addition, subtraction, multiplication, the sign function and all real constants.