Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

The multivariate resultant lies between NP and AM

Abstract : The resultant of a square system of homogeneous polynomials is a polynomial in their coefficients which vanishes whenever the system has a solution. Canny gave an algorithm running in polynomial space to compute it but no lower bound was known. We investigate the complexity of the associated decision problem and give a hardness result: Testing the resultant for zero lies in the class Arthur-Merlin and is NP-hard. We give a randomized reduction and a deterministic reduction for NP-hardness. The latter can be seen as a derandomization result.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Bruno Grenet <>
Submitted on : Friday, December 11, 2009 - 11:29:48 PM
Last modification on : Friday, September 10, 2021 - 2:34:03 PM
Long-term archiving on: : Thursday, June 17, 2010 - 9:37:27 PM


Files produced by the author(s)


  • HAL Id : ensl-00440842, version 1
  • ARXIV : 0912.2607



Bruno Grenet, Pascal Koiran, Natacha Portier. The multivariate resultant lies between NP and AM. 2009. ⟨ensl-00440842v1⟩



Record views


Files downloads