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$
Complexity of general polynomial map evaluation is polynomial?
algorithms;complexity theory;polynomial time;polynomials
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.