ON THE COMPUTATION OF BOOLEAN FUNCTIONS BY ANALOG CIRCUITS OF BOUNDEDFAN-IN

We consider the complexity of computing Boolean functions by analog ci rcuits of bounded fan-in, i.e., by circuits of gates computing real-va lued functions, either exactly or as sign-representation. Sharp upper bounds are obtained for the complexity of the most difficult n-variabl e function over certain bases (sign-representation by arithmetic circu its and exact computation by piecewise linear circuits). Bounds are gi ven for the computational power gained by adding discontinuous gate fu nctions and nondeterminism. We also prove explicit nonlinear lower bou nds for the formula size of analog circuits over bases containing addi tion, subtraction, multiplication, the sign function and all real cons tants. (C) 1997 Academic Press.