Mathematics – Algebraic Geometry
Scientific paper
2004-11-05
Mathematics
Algebraic Geometry
25 pages, 5 figures. MAJOR revision of earlier version: (1) Frederic Bihan is a new co-author, (2) Theorem 1 is strengthened w
Scientific paper
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 FEAS_R 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 FEAS_R 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+n^{epsilon} (for n varying and any fixed epsilon>0). Because of important connections between FEAS_R 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.
Bihan Frédéric
Rojas Maurice J.
Stella Casey E.
No associations
LandOfFree
First Steps in Algorithmic Fewnomial Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with First Steps in Algorithmic Fewnomial Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and First Steps in Algorithmic Fewnomial Theory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-498477