When is a problem strongly NP-complete

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)

• What does it mean for a diophantine equation to be NP-complete? NP-completeness is a category of decision problems. What decision problem do you have in mind? Commented Mar 13, 2020 at 18:16
• Thanks for your comment, NP complete is good for me! but this is a strongly NP complete. How demonstrated that this problem is strongly NP complete.
– tala
Commented Mar 14, 2020 at 13:24
• As @YuvalFilmus said, It makes no sense to say that "this diophantine equation is strongly NP-complete" because 1) you did not specify what decision problem you are interested in, and 2) (strong) NP-completeness only makes sense over classes of instances. The answer to any single (fixed) instance of any problem in NP can be found in constant time. Commented Mar 15, 2020 at 0:18
• Okay, it's true what you said. I formulate the problem: Input: A polynomial equation on n variables whose coefficients are integers (example: $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) How to prove that this diophantine equation 0/1 is strongly NP-complete?
– tala
Commented Mar 15, 2020 at 1:14
• @tala again, this instance has a fixed answer (we might not know it, but that is besides the point). Nothing to "compute", a simple look up. "Complexity" refers to the resources needed to compute answers to problems with infinite instances (if finite, a boring lookup is all what is needed). Commented Mar 19, 2020 at 2:57

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.