algorithm - 2-可满足性问题-是否存在唯一的真值分配

Question

我有一个问题是 2-SAT 问题的扩展。在标准的 2-SAT 问题中，我们可以找到任何取决于我们选择的顶点顺序的真值分配。我想检查是否存在一个且只有一个真值赋值（即只有一个组合），表达式可以满足。文字的数量可以是 100000。一种方法是找到所有可能的真值分配，然后比较它们是否不同。但问题是对于每次比较，我将不得不比较 100000 个值（没有文字）。有什么有效的方法吗？

Answer 1

Feder (1994) 描述了一种算法，用于有效地列出给定 2-satisfiability instance 的所有解决方案。文中也有引用算法来统计赋值次数，不过你只需要尝试列出两个赋值，可能效率更高。