Contatore di soluzioni di tempo polinomiale di 2sat espressione con pura letterali

Question

Secondo il titolo, esiste un algoritmo di tempo polinomiale per contare il numero di argomenti soddisfacenti per un'espressione 2sat con i puri letterali?Un caso ancora più superficiale: c'è un altro contatore quando i letterali nell'espressione sono tutti positivi o tutti negativi?

Answer 1

Contando il numero di incarichi soddisfacenti in una formula 2SAT positiva è la stessa del conteggio del numero di coperture vertice nel grafico corrispondente (dopo aver rimosso le clausole di Singleton).Il conteggio del numero di coperchi vertice è noto per essere $ \ mathsf {\ # p} $ -Complete.Vedi anche Questa domanda su cstheory.