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.
In International Colloquium on Automata, Languages and Programming (ICALP)
|Series||Lecture Notes in Computer Science|