Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

This is a constraint satisfaction problem with the additional requirement that every variable appear in at most two clauses. This is dealt with in a paper by Feder and another paper by Dalmau and Ford.

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

share|improve this answer
    
On the positive side, you can encode the problem as a SAT instance and then use a SAT solver (some of them perhaps accept CSPs directly). –  Yuval Filmus Feb 16 '11 at 6:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.