# 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? 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
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. 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
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). 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.