1
$\begingroup$

When all the input variables $a_i$ are restricted to $\{0,1\}$, how does one compute the number of solutions to equations like

$ a_1a_4a_2 + a_1a_5a_3 + a_4a_6a_3 = c $

where $c$ is a non-negative integer? The terms are not limited to trinary products, they could be greater. It is trivial to compute the above example by hand (or by enumerating with a computer), but insight to the solution process would be helpful.

Edit: In response to the comments that suggest this problem could be NP-hard, I'll accept the bounds on a solution as well.

${\bf \text{Edit}}_2 :$ Originally the problem stated that the question was over GF(2), but from the suggestions in the comments, the title of "0-1 non-linear integer program" is more accurate.

  • 0
    The use of properties of the Reed-Muller codes only applies to $GF(2)$ arithmetic, so does not apply to a version, where $1+1\neq0$, sorry.2012-02-04

1 Answers 1

1

Determining the number of solutions would be NP-Hard.

A reduction from 4-SAT would work as follows:

With each variable $x_i$ in the 4-SAT formula, we create a variable $a_i$.

$\neg x_i$ will be same as $1 + a_i$.

We transform

$x_i \text{ OR } x_j$ to $a_i + a_j + a_i a_j$.

$x_i \text{ AND } x_j$ to $a_ia_j$.

The resulting expression will be of the form $T_1 + T_2 + \dots + T_m$, where $T_r$ is of the form $a_ia_ja_k$ or $a_ia_ja_ka_l$.