1
$\begingroup$

I have a natural number $m$, and a polynomial $p: \mathbb{Z}^n \rightarrow \mathbb{Z}$, and I need to find a set $(x_1, x_2,...,x_n)$ so that $p(x_1, x_2,...,x_n) \bmod m = 0$.

First: Does every non-constant polynomial have such a set? And more importantly: Does there exist an (efficient) procedure to determine it, in case a set exists?

  • 0
    A partial answer to the first question: If $m$ is prime and the number of variables $n$ is bigger than the degree of the polynomial $p$ then by [Chevalley's Theorem](http://mathworld.wolfram.com/ChevalleysTheorem.html) the number of zeros is divisible by $p$. This might be useful if you already know a solution as in the case when there is no constant term.2011-01-25

1 Answers 1

1

If I am not mistaken, this is not known. When $m = 2$ this problem is equivalent to Boolean satisfiability (SAT for short), which is known to be NP-complete. This is because one can represent logical operations as polynomial operations on the finite field $\mathbb{F}_2$ (with $0$ being false and $1$ being true) as follows:

$\neg x = 1 - x, x \text{ and } y = xy, x \text{ or } y = x + y + xy.$

It follows that any Boolean expression in $n$ Boolean variables $x_1, ... x_n$ can be written as a polynomial over $\mathbb{F}_2$, and finding solutions is equivalent to finding a non-satisfying assignment for the Boolean expression (so replacing the expression with its negation we get the usual form of SAT). So the question of whether there exists a polynomial-time algorithm for solving this problem is equivalent to P vs. NP.

I was mistaken! Well, in any case, this paper might be relevant.

  • 0
    @Mike: whoops. Very good point.2011-01-24