2-Satisfiability問題 - 是否存在唯一的真值分配

Question

我有一個問題，它是2-SAT問題的延伸。在標準的2-SAT問題中，我們可以找到任何取決於我們選擇的頂點排序的真值分配。我想檢查是否存在唯一的表達式可滿足的真值賦值（即只有一個組合）。文字的數量可以是100000. 一種方法是找到所有可能的真值賦值，然後將它們進行比較，如果它們是不同的。但問題是每次比較，我將不得不比較100000個值（沒有文字）。有沒有什麼有效的方法？

Answer 1

Feder (1994) describes an algorithm for efficiently listing all solutions to a given 2-satisfiability instance。本文中還有引用了計算賦值次數的算法，但您只需要嘗試列出兩個賦值，這可能會更有效。