Arithmetic Circuit Size, Identity Testing, and Finite Automata
V. Arvind, Pushkar S. Joglekar · Electronic colloquium on computational complexity · 2009
Let Fhx1,x2,···,xni be the noncommutative polynomial ring over a field F, where the xi's are free noncommuting formal variables. Given a finite autom aton A with the xi's as alphabet, we can define polynomials f(mod A) and f(div A) obtained by natural operations that we call intersecting and quotienting the polynomial f by A. Related to intersection, we also define the Hadamard productfg of two polynomials f and g. In this paper we study the circuit and algebraic branching program (ABP) complexities of the polynomials f(modA), f(div A), and fg in terms of the corresponding complexities of f and g and size of the automa- ton A. We show upper and lower bound results. Our results have consequences in new polynomial identity testing algorithms (and algorithms for its corresponding s earch version of finding a nonzero monomial). E.g. we show the following: (a) A deterministic NC 2 identity test for noncommutative ABPs over rationals. In fact, we tightly classify the problem as complete for the logspace counting class C=L. (b) Randomized NC 2 algorithms for finding a nonzero monomial in both noncommuta tive and commuta- tive ABPs. (c) Over monomial algebras Fhx1,···,xni/I we derive an exponential size lower bound for ABPs com- puting the Permanent. We also obtain deterministic polynomial identity testing for ABPs over such algebras. We also study analogous questions in the commutative case and obtain some results. E.g. we show over any commutative monomial algebra Q(x1,···,xn)/I such that the ideal I is generated by o(n/lgn) monomi- als, the Permanent requires exponential size monotone circuits.