  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.
