The Multivariate Resultant is NP-hard in any Characteristic

Abstract : 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.
Type de document :
Communication dans un congrès
Petr Hlinený, Antonín Kucera. Mathematical Foundations of Computer Science 2010, Aug 2010, Brno, Czech Republic. Springer-Verlag, 6281, pp.477-488, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15155-2_42〉
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00440842
Contributeur : Bruno Grenet <>
Soumis le : jeudi 4 octobre 2012 - 15:55:20
Dernière modification le : mardi 24 avril 2018 - 13:52:35
Document(s) archivé(s) le : samedi 5 janvier 2013 - 03:59:41

Fichiers

resultant-prunel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bruno Grenet, Pascal Koiran, Natacha Portier. The Multivariate Resultant is NP-hard in any Characteristic. Petr Hlinený, Antonín Kucera. Mathematical Foundations of Computer Science 2010, Aug 2010, Brno, Czech Republic. Springer-Verlag, 6281, pp.477-488, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15155-2_42〉. 〈ensl-00440842v3〉

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

196