Examples of #P problems which are in FP ?

Question

Is there any case of SAT problems (except the affine ones) whose counting version can be computed in polynomial time ?

Answer 1

$SAT$ and $\#SAT$ for CNF formulas of bounded rank are tractable. See $[1]$.

1. Andrei S. et al. A hierarchy of tractable subclasses for SAT and counting SAT problems. 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing.

Answer 2

Yes.

Boolean Domain

For Boolean variables, the set of product type functions $\mathcal{P}$ contains functions that are products of (1) binary equality, (2) binary disequality, (3) and unary functions. Equivalently, $\mathcal{P}$ is the tensor closure of functions with support on complementary inputs. If $\mathcal{F} \subseteq \mathcal{P}$, then #CSP($\mathcal{F}$) is computable in polynomial time. This set of functions is tractable for a trivial reason. After replacing each function by its tensor product factors, in each connected component, there are only two possible assignments that can possibly be nonzero. Furthermore, the two assignment (if they exist) can be found by a two coloring algorithm.

Note that this result is not just for the unweighed version (outputs in $\\{0,1\\}$), but for any complex weights. See either

• section 5 of Jin-Yi Cai, Pinyan Lu, and Mingji Xia. Holant problems and counting csp. In STOC, pages 715–724, 2009.

for the conference version behind a paywall or

• section 3 of The Complexity of Complex Weighted Boolean #CSP - Jin-Yi Cai, Pinyan Lu, Mingji Xia

for the full (second half), which is free.

Domain Size $k$

For larger domains, there are other tractable problems as well. In this most general setting however, the dichotomy for #CSP is currently not know to be decidable.

The special case of just one binary function is known as counting graph homomorphisms. When this function is also symmetric, then there is a decidable dichotomy. While it is difficult to describe which problems are tractable, the tractability boils down to the following tractable counting problem.

If $q$ is a prime power, $\omega_q$ a $q$th root of unity, and $f(x_1, \dots, x_n)$ a quadratic polynomial over $\mathbb{Z}_q$, then

${\displaystyle \sum_{x_1, \dots, x_n \in \mathbb{Z}_q}} \omega_q^{f(x_1, \dots, x_n)}$

is computable in polynomial time (see Section 12).