2-Soddisfacibilità problem-Se un'assegnazione unica verità esiste o no

Question

Ho un problema che è un'estensione di 2-SAT problema. In serie problema 2-SAT, possiamo trovare una qualsiasi delle assegnazioni di verità che dipende l'ordine dei vertici che scegliamo. Voglio verificare se esiste una e una sola assegnazione di verità (cioè solo una combinazione) per il quale l'espressione è soddisfacibile. Il numero di letterali può essere 100.000. Un modo è quello di trovare tutte le possibili assegnazioni di verità, poi confrontarli se sono distinti. Ma il problema è per ogni confronto, dovrò confrontare 100000 valori (non di letterali). C'è un modo efficace?

Answer 1

Feder (1994) descrive un algoritmo della messa in vendita in modo efficiente tutte le soluzioni per un dato 2- esempio soddisfacibilità . Ci sono anche le citazioni nell'articolo per gli algoritmi per contare il numero di incarichi, ma avete solo bisogno di provare messa in vendita di due incarichi, che può essere più efficace.