The Multivariate Resultant is NP-hard in any Characteristic - Computer Science > Computational ComplexityReportar como inadecuado




The Multivariate Resultant is NP-hard in any Characteristic - Computer Science > Computational Complexity - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: The multivariate resultant is a fundamental tool of computational algebraicgeometry. It can in particular be used to decide whether a system of nhomogeneous equations in n variables is satisfiable the resultant is apolynomial in the system-s coefficients which vanishes if and only if thesystem is satisfiable. In this paper we present several NP-hardness resultsfor testing whether a multivariate resultant vanishes, or equivalently fordeciding whether a square system of homogeneous equations is satisfiable. Ourmain result is that testing the resultant for zero is NP-hard underdeterministic reductions in any characteristic, for systems of low-degreepolynomials with coefficients in the ground field rather than in anextension. We also observe that in characteristic zero, this problem is in theArthur-Merlin class AM if the generalized Riemann hypothesis holds true. Inpositive characteristic, the best upper bound remains PSPACE.



Autor: Bruno Grenet LIP, Pascal Koiran LIP, Natacha Portier LIP

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados