# An efficient way to check whether a polynomial (under certain condition) is absolutely equal to zero or not

We have a function $f$ of $N$ variables which is the product of $M$ polynomials: $$f(x_1,x_2,\ldots, x_N) = P_1 \cdot P_2 \cdots P_M.$$

Each $P_i$ is a polynomial of at most three variables ($x_j$s) with degree 1, and each variable appears in at most two of the $P_i$ 's, so the highest degree of each variable in $f$ is limited by $2$. Now, the question is that if we expand $f$ and then replace every $x_i^2$ with $x_i$, would the result be absolute zero or not? in other words: $$g(x_1,x_2,\ldots, x_N) = f(x_1,x_2,\ldots, x_N) \bmod (x_1^2-x_1) \bmod (x_2^2-x_2) \cdots \bmod (x_N^2-x_N)$$ is $g == 0$ or not ? (by $\bmod$ I mean polynomial remainder)

Example:

• $f = (x+y - 2xy)(y+z - 2yz)(z+x - 2zx)$.

• $g = \mathrm{remainder}(\mathrm{remainder}(\mathrm{remainder}(f , x^2-x), y^2-y), z^2-z) == 0$.

i.e. if we expand f, and then replace every $x^2$ by $x$ , $y^2$ by $y$, and $z^2$ by $z$, all the terms will cancel out and the result will be absolute zero.

The challenge is that, expanding $f$ may result in an exponential number of intermediate terms, so I'm looking for an algorithm that can test whether $g==0$ without the need to fully expand $f$. For example by assigning some numerical values to $x_i$ and evaluating $f$ or through some transformation that can simplify calculation of $g$.

Thanks, MG

-

If you really allow all possible clauses involving three variables, then you can encode 3SAT, as Feder shows: if a variable $x$ is used $n$ times, replace every use of it by $x_i$, and add consistency clauses: $$(x_1=x_2=y_1) \land (y_1=x_3=y_2) \land (y_2=x_4=y_3) \land \cdots \land (y_{n-3} = x_{n-1} = x_n).$$
Feder and Dalmau and Ford are trying to characterize the restrictions on the clauses which result in polytime-solvable problems; the latter (attributing the result to the former) have shown that if every variable is allowed to occur three times, then the problem is always NP-complete. Related work is Schaefer which does just that without the "maximum-use" constraint, and Kratochvíl which shows that for $k$-SAT, there is a jump from polytime-solvable to NP-complete, depending on the allowed number of occurrences (I'm not sure whether they give the exact number).