We study a complexity chasm for certain sparse univariate polynomials over the p-adic rationals Q_p. In particular, detecting roots in Q_p, for an input prime p and sparse univariate polynomial f in Z[x], is already known to be NP-hard with respect to randomized-reductions. Furthermore, it is known that NP-hardness (with respect to randomized reductions) also holds for detecting roots over finite fields of the form F_p. A natural question then is whether one can nevertheless have polynomial-time root detection when the number of monomial terms is fixed. Another natural question is whether polynomial-time root detection is possible for sparse univariate polynomials over the prime power ring Z/(p^k) for some fixed k≥2.

We prove a chasm, separating the trinomial and tetranomial cases, for the minimal spacing between roots in the p-adic complex numbers C_p. In particular, we show that roots in C_p are well-separated for trinomials: The spacing admits a polynomial upper bound for its p-adic valuation. On the other hand, we give explicit families of tetranomials having exponentially large p-adic valuation for the spacing of their roots in Z_p. This gives some evidence that NP-hardness for root counting in Q_p might begin with tetranomials. We also discuss the hardness of detecting roots in the ring Z/(p²).