When is a problem strongly NP-complete
This problem is strongly NP-complete; it is straightforward to reduce 3SAT to this problem.

The clause $C = (x_1 \lor \neg x_2 \lor x_3)$ can be encoded as the polynomial $p(x_1,x_2,x_3,\dots) = [(1-x_1)x_2(1-x_3)]^2$.  The conjunction of clauses $\varphi = C_1 \land \dots \land C_m$ can be encoded as $q(x_1,\dots,x_n) = p_1(x_1,\dots,x_n) \cdots p_m(x_1,\dots,x_n)$, where $p_i(x_1,\dots,x_n)$ is the encoding of clause $C_i$.  Then, the polynomial $q(x_1,\dots,x_n)$ has a solution in $\{0,1\}^n$ if and only if the original formula $\varphi$ is satisfiable.