Suppose f is an n-variate polynomial with integer coefficients and degree d. Many natural computational problems involving the real zero set Z of f are algorithmically difficult. For instance, no known algorithm for computing the number of connected components of Z has complexity polynomial in n+d. Furthermore, no known general algorithm for deciding whether f has root over the p-adic has sub-exponential complexity. So it is worthwhile to seek families of polynomials where these questions are tractable.

Assuming f has n+2 monomial terms, and its exponent vectors do not all lie on an affine hyperplane, we prove that the isotopy type of Z can be determined in time polynomial in log d, for any fixed n. (This family of polynomials --- polynomials supported on circuits ---is highly non-trivial, since it already includes Weierstrass normal forms and several important examples from semi-definite programming.) We also show that a 1998 refinement of the abc-Conjecture (by Baker) implies that our algorithm is polynomial in n as well. Furthermore, the original abc-Conjecture implies that p-adic rational roots for f can be detected in the complexity class NP.

     These results were obtained in collaboration with Kaitlyn Phillipson and Daqing Wan.