Solvability of a System of Bivariate Polynomial Equations over a Finite Field

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.