2
$\begingroup$

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

$\endgroup$
  • 10
    $\begingroup$ To answer your question literally, every FP problem where the function takes on values in the nonnegative integers is in #P. $\endgroup$ – Peter Shor Mar 28 '11 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 Ito Mar 28 '11 at 16:26
6
$\begingroup$

$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.
$\endgroup$
  • $\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$ – user4432 Mar 28 '11 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$ – Oleksandr Bondarenko Mar 28 '11 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$ – Ross Snider Mar 29 '11 at 4:01
  • $\begingroup$ Tks for your very clear answer. $\endgroup$ – user4432 Mar 29 '11 at 12:06
4
$\begingroup$

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

for the conference version behind a paywall or

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

$\endgroup$

Your Answer

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