Thumbnail
Access Restriction
Open

Author Grenet, Bruno ♦ Koiran, Pascal ♦ Portier, Natacha
Source arXiv.org
Content type Text
File Format PDF
Date of Submission 2009-12-14
Language English
Subject Domain (in DDC) Computer science, information & general works
Subject Keyword Computer Science - Computational Complexity ♦ cs
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.
Description Reference: Dans Mathematical Foundations of Computer Science 2010 - Mathematical Foundations of Computer Science 2010, Brno : Czech Republic (2010)
Educational Use Research
Learning Resource Type Thesis
Page Count 13


Open content in new tab

   Open content in new tab