  We present a deterministic 2^O(t)q^{(t-2)(t-1)+o(1)} algorithm to decide
whether a univariate polynomial f, with exactly t monomial terms and degree <q,
has a root in F_q. A corollary of our method --- the first with complexity
sub-linear in q when t is fixed --- is that the nonzero roots in F_q can be
partitioned into at most 2 \sqrt{t-1} (q-1)^{(t-2)(t-1)} cosets of two
subgroups S_1,S_2 of F^*_q, with S_1 in S_2. Another corollary is the first
deterministic sub-linear algorithm for detecting common degree one factors of
k-tuples of t-nomials in F_q[x] when k and t are fixed.
  When t is not fixed we show that each of the following problems is NP-hard
with respect to BPP-reductions, even when p is prime: (1) detecting roots in
F_p for f, (2) deciding whether the square of a degree one polynomial in F_p[x]
divides f, (3) deciding whether the discriminant of f vanishes, (4) deciding
whether the gcd of two t-nomials in F_p[x] has positive degree. Finally, we
prove that if the complexity of root detection is sub-linear (in a refined
sense), relative to the straight-line program encoding, then NEXP is not in
P/Poly.
