期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We say that a polynomial f(x1xn) is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that for multilinear polynomials, factorization is the same as decomposition, as any two different factors are variable disjoint.
In this paper we show that the problem of derandomizing polynomial identity testing is essentially equivalent to the problem of
derandomizing algorithms for polynomial decomposition. More accurately, we show that for any reasonable circuit class there is
a deterministic polynomial time (black-box) algorithm for polynomial identity testing of that class if and only if there is
a deterministic polynomial time (black-box) algorithm for factoring a polynomial, computed in the class, to its indecomposable components.
An immediate corollary is that polynomial identity testing and polynomial factorization are equivalent (up to a polynomial overhead) for multilinear polynomials. In addition, we observe that derandomizing the polynomial decomposition problem is equivalent, in the sense of Kabanets and Impagliazzo, to proving arithmetic circuit lower bounds to NEXP.
Our approach uses ideas from a previous work in which we showed that the polynomial identity testing problem for a circuit class is essentially equivalent to the problem of deciding whether a circuit from computes a polynomial that has a read-once arithmetic formula.
