The multivariate resultant lies between NP and AM - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

The multivariate resultant lies between NP and AM


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.
Fichier principal
Vignette du fichier
resultant-prunel.pdf (175.21 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

ensl-00440842 , version 1 (11-12-2009)
ensl-00440842 , version 2 (03-06-2010)
ensl-00440842 , version 3 (04-10-2012)



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



Gmail Facebook Twitter LinkedIn More