Problem:
Let $X=\{x_1, ..., x_N \}$ be a set of binary variables. Each variable can be assigned to either $0$ or $1$ so there are $2^N$ possible assignments.
Input: We are given a positive integer $C$ and a set of binary functions $F=\{f_1,...,f_M\}$ where each function is defined as a simple conjunction of some subset of $X$. That is, each $f_i \in F$ is defined as $f_i(X) := \prod_{x \in X'}x$ for some $X' \subseteq X$.
Output: The number of assignments to variables in $X$ such that $\sum_{i=1}^M f_i(X) = C$.
Question:
Do you know of a polynomial-time algorithm that solves this problem for a bounded value of $C$?
Any ideas or pointers to references would also be greatly appreciated.
It is OK if the complexity is bounded with respect to e.g. some constant $D$ which could be the maximum size of $X'$, that is, the maximum number of variables in the product of any function $f_i \in F$.
Observations:
When $|X'|=1$, that is, when each function $f_i \in F$ can only have one variable, then the problem can be reduced to the counting version of the subset sum problem and can be solved in $\mathcal{O}(N\cdot C)$ time using an modified version of a dynamic programming algorithm for solving subset sum.
