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