4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What can you say about the case $C = 0$? $\endgroup$ Apr 24 '21 at 19:17
  • $\begingroup$ At first, I thought it was trivial (one solution is $X = \{0,...,0\}$), but I realize there could be multiple solutions. Therefore I think it's an interesting case. $\endgroup$
    – boka
    Apr 24 '21 at 19:22
1
$\begingroup$

When $C = 0$ and each $f_i$ depends on two inputs, your problem is equivalent to #2-MONOTONE-SAT, which is #P-complete, see for example this question on cstheory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.