When is a problem strongly NP-complete

Question

Let the problem of the diophantic equation 0/1 be as follows.

Input : A polynomial equation on n variables whose coefficients are integers (ex : $2x^3_1 x_2 + x_1x^3_3 - 3x_4 = 8$)

Question: Does this equation have a solution in space {0,1}$^n$ ? (can we satisfy the equation by choosing for each variable the value 0 or 1?)

1 - How to prove that this diophantine equation 0/1 is NP-complete?

2 - How to prove that this diophantine equation 0/1 is Strongly NP-complete (ie its restriction to the case where all the coefficients are bounded by a polynomial of the number of variables is already NP-complete)

Answer 1

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.