  The Shub-Smale Tau Conjecture is a hypothesis relating the number of integral
roots of a polynomial f in one variable and the Straight-Line Program (SLP)
complexity of f. A consequence of the truth of this conjecture is that, for the
Blum-Shub-Smale model over the complex numbers, P differs from NP. We prove two
weak versions of the Tau Conjecture and in so doing show that the Tau
Conjecture follows from an even more plausible hypothesis.
  Our results follow from a new p-adic analogue of earlier work relating real
algebraic geometry to additive complexity. For instance, we can show that a
nonzero univariate polynomial of additive complexity s can have no more than
15+s^3(s+1)(7.5)^s s! =O(e^{s\log s}) roots in the 2-adic rational numbers Q_2,
thus dramatically improving an earlier result of the author. This immediately
implies the same bound on the number of ordinary rational roots, whereas the
best previous upper bound via earlier techniques from real algebraic geometry
was a quantity in Omega((22.6)^{s^2}).
  This paper presents another step in the author's program of establishing an
algorithmic arithmetic version of fewnomial theory.
