Is there any case of SAT problems (except the affine ones) whose counting version can be computed in polynomial time ?
$\begingroup$
$\endgroup$
2
-
11$\begingroup$ To answer your question literally, every FP problem where the function takes on values in the nonnegative integers is in #P. $\endgroup$– Peter ShorMar 28, 2011 at 14:23
-
7$\begingroup$ You are asking one question in the title and another (though related) question in the body. I do not think that it is a good practice because it makes unclear what counts as a valid answer. See also: Ask a focused question that has a specific goal. $\endgroup$– Tsuyoshi ItoMar 28, 2011 at 16:26
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
$SAT$ and $\#SAT$ for CNF formulas of bounded rank are tractable. See $[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.
answered Mar 28, 2011 at 12:02
-
$\begingroup$ In the reference $[1]$ above, all formulas of bounded rank are tractable. Does it mean it is np-hard to decide which rank a formula is ? $\endgroup$– user4432Mar 28, 2011 at 21:31
-
$\begingroup$ @Ariston: On p. 64 the following can be found: "the membership problem (“Is $F$ a $Rank_k$ formula?”) can be solved in polynomial time." $\endgroup$ Mar 28, 2011 at 23:10
-
2$\begingroup$ @Ariston: I am answering what I think you were asking. This is very much like finding cliques. Finding a clique of any fixed 'k' can be done in polynomial time O(n^k). However it requires "fixed" k - as the size of the graph grows the size of the clique can grow. Similarly the rank of a formula is not bounded; it can grow like cliques in a graph. $\endgroup$ Mar 29, 2011 at 4:01
-
$\begingroup$ Tks for your very clear answer. $\endgroup$– user4432Mar 29, 2011 at 12:06
$\begingroup$
$\endgroup$
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).
answered Aug 31, 2011 at 16:02