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
    It seems a bit strange to talk about $\mathbb{GF}(2)$, and have the right hand side be an integer other than $0,1$. In any case, this is likely to be NP-Hard, probably a reduction from SAT. (Choosing to comment, as I am not sure, as the + becomes XOR).2012-02-03
  • 0
    Well, if this is an equation over GF(2), then also $c\in GF(2)$ :-). Anyway the number of solution is also the weight of a word of a certain Reed-Muller code. That helps a little (gives an upper and a lower bound in terms of the degree of the l.h.s. and the total number of variables).2012-02-03
  • 0
    @Aryabhata perhaps. I'd welcome a rephrasing of the question if it would make it more clear. What I intended to say was that only the input variables $a_i$, are restricted to $\{0,1\}$.2012-02-03
  • 0
    @Hooked: You can call it 0-1 non-linear integer program I guess, similar to the commonly called 0-1 integer programming problem...2012-02-03
  • 0
    Hooked, in $GF(2)$ we have $1+1=0$. So are you really looking at the equation in the ring of integers, but restrict the variables to the set $\{0,1\}$?2012-02-03
  • 0
    @JyrkiLahtonen, yes that is correct. I've removed the references to GF(2). Based off the comments above I don't think I meant GF(2) at all, just a restriction on the possible values for $a_i$. Do you think you could elaborate on the bounds from the Reed-Muller code you mentioned?2012-02-04
  • 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$.