We study the following problem - given a finite field F and a set of polynomials p1(x), p2(x), ... , pm(x) in n variables x=(x1, ..., xn) over F, determine if the corresponding system of equations

p1(x) = p2(x) = ... = pm(x) = 0

has a solution over F or not. We investigate the complexity of this problem when the number of variables is bounded. We show that for any fixed value of n, there is a deterministic algorithm for deciding solvability whose running time is bounded by a polynomial in d, m and log |F|. Previously, only a randomized polynomial-time algorithm was known (Huang and Wong, FOCS 1996). In particular, this result also leads to a deterministic algorithm for recognizing permutation functions, a problem which was previously known to be in ZPP (Ma and Gathen, STOC 1994) but not known to be in P.

PDF file

In  International Colloquium on Automata, Languages and Programming (ICALP)

Publisher  Springer

Details