Computational calssification of multivariate polynomials using symmetries and reductions

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.