Calcolo del numero di incarichi che soddisfano una formula proposizionale generale
-
05-11-2019 - |
Domanda
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?
Nessuna soluzione corretta