2-Satisfiabilité problème Si une instanciation unique existe ou non

Question

me pose un problème qui est une extension du problème 2-SAT. Dans problème standard 2-SAT, nous pouvons trouver des missions de vérité qui dépend de l'ordre des sommets que nous choisissons. Je veux vérifier s'il existe une et une seule affectation de vérité (i.e. une seule combinaison) pour laquelle l'expression est satisfiable. Le nombre de littéraux peut être 100000. Une façon est de trouver toutes les affectations possibles de vérité, puis les comparer si elles sont distinctes. Mais le problème est pour chaque comparaison, je dois comparer les valeurs 100000 (pas de littéraux). Y at-il moyen efficace?

Answer 1

Feder (1994) décrit un algorithme de liste efficacement toutes les solutions à une donnée 2- par exemple satisfiability . Il y a aussi des citations dans l'article pour les algorithmes pour compter le nombre de missions, mais il vous suffit d'essayer la liste deux affectations, qui peut être plus efficace.