SOME RESULTS ON UNIFORM ARITHMETIC CIRCUIT COMPLEXITY

We introduce a natural set of arithmetic expressions and define the co mplexity class AE to consist of all those arithmetic functions (over t he field F-2n) that are described by these expressions. We show that A E coincides with the class of functions that are computable with const ant depth and polynomial-size unbounded fan-in arithmetic circuits sat isfying a natural uniformity constraint (DLOGTIME-uniformity). A 1-inp ut and 1-output arithmetic function over the fields F-2n may be identi fied with an n-input amd n-output Boolean function when field elements are represented as bit strings. We prove that if some such representa tion is X-uniform (where X is P or DLOGTIME), then the arithmetic comp lexity of a function measured with X-uniform unbounded fan-in arithmet ic circuits) is identical to the Boolean complexity of this function ( measured with X-uniform threshold circuits). We show the existence of a P-uniform representation and we give partial results concerning the existence of representations with more restrictive uniformity properti es.