期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The work in this paper is to initiate a theory of testing
monomials in multivariate polynomials. The central question is to
ask whether a polynomial represented by certain economically
compact structure has a multilinear monomial in its sum-product
expansion. The complexity aspects of this problem and its variants
are investigated with two folds of objectives. One is to
understand how this problem relates to critical problems in
complexity, and if so to what extent. The other is to exploit
possibilities of applying algebraic properties of polynomials to
the study of those problems. A series of results about
and polynomials are obtained in this
paper, laying a basis for further study along this line.
