2-Erfüllbarkeit Problem Ob eine einzigartige Wahrheit Zuordnung vorhanden ist oder nicht

Question

Ich habe ein Problem, das ist eine Erweiterung von 2-SAT Problem. Im Standard-2-SAT Problem, wir können eine der Wahrheit Zuweisungen finden, die auf der Bestellung von Eckpunkten ab, die wir wählen. Ich möchte überprüfen, ob es existiert eine und nur eine Wahrheit Zuordnung (das heißt nur eine Kombination), für die der Ausdruck erfüllbar ist. Die Zahl der Literale können 100000 sein. Eine Möglichkeit ist, alle möglichen Wahrheitszuweisungen zu finden, dann vergleichen sie, wenn sie verschieden sind. Aber das Problem ist für jeden Vergleich, werde ich 100000 Werte vergleichen haben (keine von Literalen). Gibt es eine effiziente Art und Weise?

Answer 1

Feders (1994) beschreibt einen Algorithmus zum effizienten Auflistung aller Lösungen zu einem bestimmten 2- Erfüllbarkeit Instanz . Darüber hinaus gibt es Zitate in dem Artikel für Algorithmen, um die Anzahl der Zuordnungen zu zählen, aber Sie müssen nur versuchen, zwei Zuweisungen Auflistung, die effizienter sein kann.