Skip to Main content Skip to Navigation
Journal articles

On the Complexity of the Multivariate Resultant

Abstract : The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of n homogeneous equations in n variables is satisfiable (the resultant is a polynomial in the system's coefficients which vanishes if and only if the system is satisfiable). In this paper, we investigate the complexity of computing the multivariate resultant. First, we study the complexity of testing the multivariate resultant for zero. Our main result is that this problem is NP-hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). In characteristic zero, we observe that this problem is in the Arthur-Merlin class AM if the generalized Riemann hypothesis holds true, while the best known upper bound in positive characteristic remains PSPACE. Second, we study the classical algorithms to compute the resultant. They usually rely on the computation of the determinant of an exponential-size matrix, known as Macaulay matrix. We show that this matrix belongs to a class of succinctly representable matrices, for which testing the determinant for zero is proved PSPACE-complete. This means that improving Canny's PSPACE upper bound requires either to look at the fine structure of the Macaulay matrix to find an ad hoc algorithm for computing its determinant, or to use altogether different techniques.
Complete list of metadata
Contributor : Bruno Grenet Connect in order to contact the contributor
Submitted on : Tuesday, October 23, 2012 - 9:41:41 AM
Last modification on : Saturday, September 11, 2021 - 3:17:27 AM

Links full text





Bruno Grenet, Pascal Koiran, Natacha Portier. On the Complexity of the Multivariate Resultant. Journal of Complexity, Elsevier, 2013, 29 (2), p. 142-157. ⟨10.1016/j.jco.2012.10.001⟩. ⟨ensl-00744385⟩



Record views