The multivariate resultant lies between NP and AM - ENS de Lyon - École normale supérieure de Lyon Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2009

The multivariate resultant lies between NP and AM

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

Bruno Grenet, Pascal Koiran, Natacha Portier. The multivariate resultant lies between NP and AM. 2009. ⟨ensl-00440842v1⟩
193 Consultations
635 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More