dc.contributor.author Sturtivant, Carl dc.date.accessioned 2013-04-05T11:15:47Z dc.date.available 2013-04-05T11:15:47Z dc.date.issued 1983 dc.identifier.uri http://hdl.handle.net/1842/6642 dc.description.abstract An examination of some properties that interrelate the computational en_US 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. dc.language.iso en en_US dc.publisher The University of Edinburgh en_US dc.relation.hasversion Sturtivant, C. Generalised Symmetries of Polynomials in Algebraic Complexity. Proc. 23rd IEEE Symp. on Foundations on Computer Science (1982) 72-79. en_US dc.subject polynomial functions en_US dc.subject equivalence relations en_US dc.subject symmetries en_US dc.title Computational calssification of multivariate polynomials using symmetries and reductions en_US dc.type Thesis or Dissertation en_US dc.type.qualificationlevel Doctoral en_US dc.type.qualificationname PhD Doctor of Philosophy en_US
﻿