On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-In

摘要

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 sign-representation. Sharpupper boundsare obtained for the complexity of the most difficultn-variable function over certain bases (sign-representation by arithmetic circuits and exact computation by piecewise linear circuits). Bounds are given for the computational power gained by addingdiscontinuousgate functions andnondeterminism. We also prove explicitnonlinear lower boundsfor theformula sizeof analog circuits over bases containing addition, subtraction, multiplication, the sign function and all real constants.