2
$\begingroup$

I know, for a disjunctive clause of the form $x_1 \vee ... \vee x_i$, the number of assignments satisfying it is simply $2^i - 1$, but what about for a general formula? Is the number of satisfying assignments be calculated polynomially?

In Papadimitriou's Computational Complexity (p. 301), when explaining an approximation algorithm for $k$-MAXGSAT where the input is, over $n$ variables, $\Phi = \{\phi_1, ..., \phi_n\}$ with $\phi_i$ being any general formula involving at most $k$ variables, it is stated that

... Each expression $\phi_i \in \Phi$ involves $k$ Boolean variables. Out of the $2^k$ truth assignments, we can easily calculate the number $t_i$ of truth assignments that satisfy $\phi_i$. ...

But I don't find it obvious how one can compute it easily, as even with Tseitin's method, the transformed result of $\phi_i$ wouldn't necessarily be a single disjunctive clause. Where did I go wrong?

$\endgroup$
  • 1
    $\begingroup$ Are you sure the $\phi_i$'s are general formulas? If the number of satisfying assignments of a generic formula can be calculated in polynomial time, then (besides other things) $\textbf{P} = \textbf{NP}$... Either that or $k$ is constant w.r.t. $n$ (and then calculating the truth assignments obviously only takes constant time w.r.t. $n$). $\endgroup$ – dkaeae Feb 20 at 9:38
  • $\begingroup$ @dkaeae Oh my god! Yes you’re right! I re-read the earlier paragraph o the text and now I feel so dumb being stuck at this problem for so many days haha! Could you make it an answer and I will edit it and fill in the earlier paragraph so that I could accept your answer? $\endgroup$ – RexYuan Feb 20 at 10:40
  • 1
    $\begingroup$ @RexYuav It happens :) $\endgroup$ – dkaeae Feb 20 at 12:06
4
$\begingroup$

As I have mentioned in the comments, being able to determine the number of truth assignments of a generic formula in polynomial time would imply not only $\textbf{P} = \textbf{NP}$ but actually the much, much stronger $\textbf{#P} = \textbf{P}$ (see Yuval Filmus' answer).

What Papadimitriou really means in this context is that the number of truth assignments of each $\phi_i$ depends on the value of only $k$ variables, with $k$ being constant with respect to $n$. Thus, determining the number of truth assignments can be done in constant time (relative to $n$, not to $k$; for a more precise runtime bound, see again Yuval Filmus' answer).

For reference, here is the earlier paragraph from the text (emphasis mine):

In this problem we are given a set of Boolean expressions $\Phi = \{ \phi_1 , ... , \phi_m \}$ in $n$ variables, where each [...] is a general Boolean expression involving at most $k$ of the $n$ Boolean variables, where $k > 0$ is a fixed constant [...]

$\endgroup$
3
$\begingroup$

Counting the number of satisfying assignments in known as #SAT, and is the canonical #P-complete problem. In particular, we don't expect it to be possible to count the number of satisfying assignments of a $k$-variable formula of size $m$ in much better than $O(2^km)$. In contrast, an $O(2^km)$ algorithm does exist – just try all possible assignments.

$\endgroup$
  • $\begingroup$ Other than the degenerate case where it's just a disjunctive clause, is there any variation of #SAT that exploits for example formula structure? $\endgroup$ – RexYuan Feb 20 at 15:50
  • $\begingroup$ Wikipedia mentions some such cases. $\endgroup$ – Yuval Filmus Feb 20 at 16:18

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.