Show simple item record

dc.contributor.authorSturtivant, Carl
dc.date.accessioned2013-04-05T11:15:47Z
dc.date.available2013-04-05T11:15:47Z
dc.date.issued1983
dc.identifier.urihttp://hdl.handle.net/1842/6642
dc.description.abstractAn 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.en_US
dc.language.isoenen_US
dc.publisherThe University of Edinburghen_US
dc.relation.hasversionSturtivant, C. Generalised Symmetries of Polynomials in Algebraic Complexity. Proc. 23rd IEEE Symp. on Foundations on Computer Science (1982) 72-79.en_US
dc.subjectpolynomial functionsen_US
dc.subjectequivalence relationsen_US
dc.subjectsymmetriesen_US
dc.titleComputational calssification of multivariate polynomials using symmetries and reductionsen_US
dc.typeThesis or Dissertationen_US
dc.type.qualificationlevelDoctoralen_US
dc.type.qualificationnamePhD Doctor of Philosophyen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record