  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.
