2-Problème de fiabilité-Si une affectation de vérité unique existe ou non

Question

J'ai un problème qui est une extension du problème 2-SAT. Dans le problème standard 2-SAT, nous pouvons trouver l'une des affectations 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 assignation de vérité (c'est-à-dire une seule combinaison) pour laquelle l'expression est satisfiable. Le nombre de littéraux peut être de 100000. Une manière consiste à trouver toutes les affectations de vérité possibles, puis de les comparer si elles sont distinctes. Mais le problème est pour chaque comparaison, je vais devoir comparer 100000 valeurs (non de littéraux). Y a-t-il un moyen efficace?

Answer 1

Feder (1994) describes an algorithm for efficiently listing all solutions to a given 2-satisfiability instance. Il y a également des citations dans l'article pour les algorithmes pour compter le nombre d'affectations, mais vous avez seulement besoin d'essayer de répertorier deux affectations, ce qui peut être plus efficace.