期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Given a multivariate polynomial f(x) in F[x] as an arithmetic circuit we would like to efficiently determine:
(i) [Identity Testing.] Is f(x) identically zero?
(ii) [Degree Computation.] Is the degree of the
polynomial f(x) at most a given integer d.
(iii) [Polynomial Equivalence.] Upto an invertible linear transformation of its variables, is f(x) equal to a given polynomial g(x).
The algorithmic complexity of these problems is studied. Some new algorithms are provided here while some known ones are simplified. For the first problem, a deterministic algorithm is presented for the special case where the input circuit is a "sum of powers of sums of univariate polynomials". For the second problem, a \coRP\PP-algorithm is presented. Finally, randomized polynomial-time algorithms are presented for certain special cases of the third problem.
