期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let \F x 1 x 2 x n be the noncommutative polynomial ring over a field \F , where the x i 's are free noncommuting formal variables. Given a finite automaton \A with the x i 's as alphabet, we can define polynomials \f ( modA ) and \f ( divA ) obtained by natural operations that we call \emph{intersecting} and \emph{quotienting} the polynomial f by \A . Related to intersection, we also define the \emph{Hadamard product} f g 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 ( divA ) , and f g in terms of the corresponding complexities of f and g and size of the automaton \A . We show upper and lower bound results. Our results have consequences in new polynomial identity testing algorithms (and algorithms for its corresponding search version of finding a nonzero monomial). E.g.\ we show the following: \begin{itemize} \item[(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 . \item[(b)] Randomized \NC 2 algorithms for finding a nonzero monomial in both noncommutative and commutative ABPs. \item[(c)] Over monomial algebras \F x 1 x n I we derive an exponential size lower bound for ABPs computing the Permanent. We also obtain deterministic polynomial identity testing for ABPs over such algebras. \end{itemize} We also study analogous questions in the \emph{commutative} case and obtain some results. E.g.\ we show over any commutative monomial algebra \Q [ x 1 x n ] I such that the ideal I is generated by o ( n lg n ) monomials, the Permanent requires exponential size monotone circuits.
x 1 
