Complexity of general polynomial map evaluation is polynomial?

Question

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$

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.