## Computational calssification of multivariate polynomials using symmetries and reductions

##### View/Open

##### Date

1983##### Author

Sturtivant, Carl

##### Metadata

##### Abstract

An examination of some properties that interrelate the computational
complexities of evaluating multivariate polynomial functions is presented.
The kind of relationship between polynomial functions that is studied takes
the form of linear transformations of the arguments and results of a
polynomial function that transform it into another such function. Such
transformations are a generalisation of projection (a form of reduction
in algebraic complexity first introduced by Valiant, whereby variables
and constants are substituted for the arguments of a polynomial function
in order to transform it into another polynomial function). In particular,
two restricted forms of this generalised projection are considered: firstly,
those that relate a polynomial function to itself, and secondly, those that
are invertable. Call these symmetries and similarities, respectively.
The structure of the set of symmetries of a polynomial function is explored,
and the computationally useful members of the set identified; a technique
for finding all such symmetries is presented. It is shown that polynomials
related by similarity have "isomorphic" sets of symmetries, and this condition
may be used as a criterion for similarity. Similarity of polynomial
functions is shown to be an equivalence relation, and "similar polynomials"
can be seen to possess closely comparable complexities. A fast probabilistic
algorithm for finding the symmetries of a polynomial function is given.
The symmetries of the determinant and of the permanent (which differs from the
determinant only in that all of its monomials have coefficients of +1),
and those of some other polynomials, are explicitly found using the above
theory. Fast algorithms using linear algebra for evaluating the determinant
are known, whereas evaluating the permanent is known to be a #p-complete
problem, and is apparently intractable; the reasons for this are exposed.
As an easy corollary it is shown that the permanent is not preserved by any
bilinear product of matrices, in con'trast to the determinant which is
preserved by matrix multiplication. The result of Marcus and Minc, that the
determinant cannot be transformed into the permanent by substitution of linear
combinations of variables for its arguments (i.e. the permanent and
determinant are not similar), also follows as an easy corollary. The relationship
between symmetries and ease of evaluation is discussed.