The Multivariate Resultant is NP-hard in any Characteristic - ENS de Lyon - École normale supérieure de Lyon Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

The Multivariate Resultant is NP-hard in any Characteristic

Résumé

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 present several NP-hardness results for testing whether a multivariate resultant vanishes, or equivalently for deciding whether a square system of homogeneous equations is satisfiable. Our main result is that testing the resultant for zero 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). We also observe that in characteristic zero, this problem is in the Arthur-Merlin class AM if the generalized Riemann hypothesis holds true. In positive characteristic, the best upper bound remains PSPACE.
Fichier principal
Vignette du fichier
resultant-prunel.pdf (197.13 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 is NP-hard in any Characteristic. Mathematical Foundations of Computer Science 2010, Aug 2010, Brno, Czech Republic. pp.477-488, ⟨10.1007/978-3-642-15155-2_42⟩. ⟨ensl-00440842v2⟩
193 Consultations
635 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More