期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-36
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Equivalence testing for a polynomial family {gm}m∈N over a field F is the following problem: Given black-box access to an n-variate polynomial f(x), where n is the number of variables in gm for some m ∈ N, check if there exists an A ∈ GL(n,F) such that f(x) = gm(Ax). If yes, then output such an A. The complexity of equivalence testing has been studied for a number of important polynomial families, including the determinant (Det) and the family of iterated matrix multiplication polynomials. Two popular variants of the iterated matrix multiplication polynomial are: IMMw,d (the (1, 1) entry of the product of d many w × w symbolic matrices) and Tr-IMMw,d (the trace of the product of d many w × w symbolic matrices). The families – Det, IMM and Tr-IMM – are VBP-complete under p-projections, and so, in this sense, they have the same complexity. But, do they have the same equivalence testing complexity? We show that the answer is “yes" for Det and Tr-IMM (modulo the use of randomness). The above result may appear a bit surprising as the complexity of equivalence testing for IMM and that for Det are quite different over Q: a randomized polynomial-time equivalence testing for IMM over Q is known [KNST19], whereas [GGKS19] showed that equivalence testing for Det over Q is integer factoring hard (under randomized reductions and assuming GRH). To our knowledge, the complexity of equivalence testing for Tr-IMM was not known before this work. We show that, despite the syntactic similarity between IMM and Tr-IMM, equivalence testing for Tr-IMM and that for Det are randomized polynomial-time Turing reducible to each other over any field of characteristic zero or sufficiently large. The result is obtained by connecting the two problems via another well-studied problem in computer algebra, namely the full matrix algebra isomorphism problem (FMAI). In particular, we prove the following: 1. Testing equivalence of polynomials to Tr-IMMw,d , for d ≥ 3 and w ≥ 2, is randomized polynomial-time Turing reducible to testing equivalence of polynomials to Detw, the determinant of the w × w matrix of formal variables. (Here, d need not be a constant.) 2. FMAI is randomized polynomial-time Turing reducible to equivalence testing (in fact, to tensor isomorphism testing) for the family of matrix multiplication tensors {Tr-IMMw,3}w∈N. These results, in conjunction with the randomized poly-time reduction (shown in [GGKS19]) from determinant equivalence testing to FMAI, imply that the four problems – FMAI, equivalence testing for Tr-IMM and for Det, and the 3-tensor isomorphism problem for the family of matrix multiplication tensors – are randomized poly-time equivalent under Turing reductions.
