# Calculating the number of assignments satisfying a general propositional formula

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?

• 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$). – dkaeae Feb 20 at 9:38
• @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? – RexYuan Feb 20 at 10:40
• @RexYuav It happens :) – dkaeae Feb 20 at 12:06

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