Calculating the number of assignments satisfying a general propositional formula

Question

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?

Answer 1

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

Answer 2

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.