# Model Counting for Sum of Conjunctive Formulas

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

• What can you say about the case $C = 0$? Apr 24 '21 at 19:17
• 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.
– boka
Apr 24 '21 at 19:22

## 1 Answer

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.