我有一个问题是 2-SAT 问题的扩展。在标准的 2-SAT 问题中，我们可以找到任何真值分配，这取决于我们选择的顶点顺序。我想检查是否存在一个且只有一个表达式可满足的真值赋值(即只有一个组合)。文字的数量可以是 100000。 一种方法是找到所有可能的真值分配，然后比较它们是否不同。但问题是每次比较，我都必须比较 100000 个值(没有文字)。有什么有效的方法吗？
最佳答案
Feder (1994) describes an algorithm for efficiently listing all solutions to a given 2-satisfiability instance .文章中也有引用统计赋值次数的算法，但你只需要尝试列出两个赋值，这样可能效率更高。
关于algorithm - 2-可满足性问题-唯一真值赋值是否存在，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1665001/