Calcolo del numero di incarichi che soddisfano una formula proposizionale generale

Question

Lo so, per una clausola disgiuntiva della forma $ x_1 vee ... vee x_i $, il numero di incarichi che lo soddisfano è semplicemente $ 2^i - 1 $, ma per quanto riguarda una formula generale? Il numero di incarichi soddisfacenti è calcolato polinomia?

Nella complessità computazionale di Papadimitriou (p. 301), quando si spiega un algoritmo di approssimazione per $ k $-Maxgsat dove si trova l'ingresso $ n $ variabili, $ Phi = { phi_1, ..., phi_n } $ insieme a $ phi_i $ Essere una formula generale che coinvolge al massimo $ k $ variabili, si dice

... ogni espressione $ phi_i in phi $ coinvolge $ k $ Variabili booleane. Fuori da $ 2^k $ Assegnazioni della verità, possiamo facilmente calcolare il numero $ t_i $ di incarichi di verità che soddisfano $ phi_i $. ...

Ma non trovo ovvio come si possa calcolarlo facilmente, come anche con il metodo di Tseitin, il risultato trasformato di $ phi_i $ non sarebbe necessariamente una singola clausola disgiuntiva. Dove ho sbagliato?