A polynomial map is equal to another polynomial map iff they take on the same values at each point. So this is different from formal polynomials. So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x \neq 0$, and is $0$ on $0$, we have that there are a finite number of polynomial maps in $\Bbb{Z}_p[x_1, \dots, x_k]$. For now let's work in $\Bbb{Z}_2$ for simplicity.

The coefficients are arbitrarily chosen $c_i \in \Bbb{Z}_2$, and polynomials are in $\Bbb{Z}_2[x_1, \dots, x_k]$. Then

$c_0 + c_1x_1$ obviously has complexity $2$ (2 operations explicitly required).

$c_0 + c_1x_1 + c_2 x_2$ needs $4$ ops.

$c_0 + c_1x_1 + (c_2+ c_3 x_1) x_2$ needs $6$ ops max.

$c_0 + c_1x_1 + c_2 x_2 + c_3 x_3 + c_4 x_1 x_2 + c_5 x_1 x_3 + c_6 x_2 x_3 + c_7 x_1 x_2 x_3 = \\ c_0 + x_1(c_1 + x_2 (c_4 + c_7 x_3) + c_5 x_3) + x_2 (c_2 + c_6 x_3) + c_3 x_3$

needs $14$ ops. The pattern seems to be

$1 + (k + (k-1) + \dots + 1) + ((k-2) + (k-1) + \dots + 1) + \dots + 1$ which is $O(k^3)$, so is polynomial complexity polynomial?

Where did I make any mistake? Thanks.

This doesn't make sense as there are about $p^k$ coefficients, and each one must be visited.

$* + x_1(* + x_2(* + x_3(* + *x_4) + *x_3 + *x_4)) + x_2 (* + x_3(* + *x_4) + *x_4) + x_3(* + *x_4) + *x_4$


1 Answer 1


You are basically doing an induction definition on $k$, where you evaluate a polynomial in $k+1$ variables by evaluation two polynomials of $k$ variables (by removing $x_1$.) So you have that the complexity $f(k+1)\approx 2f(k)$, which doesn't look polynomial to me.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.