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 metadatas

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00440842
Contributor : Bruno Grenet <>
Submitted on : Friday, December 11, 2009 - 11:29:48 PM
Last modification on : Friday, January 25, 2019 - 3:34:10 PM
Long-term archiving on : Thursday, June 17, 2010 - 9:37:27 PM

Files

resultant-prunel.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

17

Files downloads

112