__
TR10-114 | 17th July 2010 23:06
__

#### The Complexity of Testing Monomials in Multivariate Polynomials

**Abstract:**
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

$\Pi\Sigma\Pi$ and $\Pi\Sigma$ polynomials are obtained in this

paper, laying a basis for further study along this line.