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 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.
Inthis note, we demonstrate that a certain class of naturally occuring problems involving an oracle are solvable in random polynomial time, but not in deterministic polynomial time. This class of problems is especially interesting because a very slight change in the parameters of the problem yields one that does have a polynomial solution. The problem of k-SAT is to determine if the given k-CNF has a satisfying solution. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k 3.Define s_k (for k 3) to be the infimum of : there exists an O(2^ n ) algorithm for solving k-SAT . Define ETH (Exponential-Time Hypothesis) for k-SAT as follows: for k 3, s_k >0. In other words, for k 3, k-SAT does not have a subexponential-time algorithm.In this paper, we show that s_k is an increasing sequence assuming for k-SAT. Let s_ be the limit of s_k. We will in fact show that s_k (1-d (ek))s_ for some constant d >0.