2004/11/05 by Frédéric Bihan, Bihan, Frederic, J. Maurice Rojas +3
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Algebraic Geometry (math.AG) #Commutative Algebra (math.AC) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Methods and Algorithms #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.math/0411107
openalex publication_date 2004/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Fewnomial theory began with explicit bounds -- solely in terms of the number of variables and monomial terms -- on the number of real roots of systems of polynomial equations. Here we take the next logical step of investigating the corresponding existence problem: Let FEASR denote the problem of deciding whether a given system of multivariate polynomial equations with integer coefficients has a real root or not. We describe a phase-transition for when m is large enough to make FEASR be NP-hard, when restricted to inputs consisting of a single n-variate polynomial with exactly m monomial terms: polynomial-time for m<=n+2 (for any fixed n) and NP-hardness for m<=n+nepsilon (for n varying and any fixed epsilon>0). Because of important connections between FEASR and A-discriminants, we then study some new families of A-discriminants whose signs can be decided within polynomial-time. (A-discriminants contain all known resultants as special cases, and the latter objects are central in algorithmic algebraic geometry.) Baker's Theorem from diophantine approximation arises as a key tool. Along the way, we also derive new quantitative bounds on the real zero sets of n-variate (n+2)-nomials.