Calcul du nombre d'affectations satisfaisant à une formule propositionnelle générale

Question

Je sais, pour une clause disjonctive du formulaire $ x_1 vee ... vee x_i $, le nombre d'affectations le satisfaisant est simplement 2 $ ^ i - 1 $, mais qu'en est-il pour une formule générale? Le nombre de missions satisfaisantes est-elle calculée polynomiale?

Dans la complexité de calcul de Papadimitriou (p. 301), lors de l'explication d'un algorithme d'approximation pour $ k $-Maxgsat où se trouve l'entrée, sur $ n $ variables, $ Phi = { phi_1, ..., phi_n } $ avec $ phi_i $ étant une formule générale impliquant au plus $ k $ variables, il est indiqué que

... chaque expression $ phi_i in phi $ implique $ k $ Variables booléennes. Hors de 2 $ ^ k $ affectations de vérité, nous pouvons facilement calculer le nombre $ t_i $ des affectations de vérité qui satisfont $ phi_i $. ...

Mais je ne trouve pas évident comment on peut le calculer facilement, comme même avec la méthode de Tseitin, le résultat transformé de $ phi_i $ ne serait pas nécessairement une clause disjonctive unique. Où est-ce que je me suis trompé?