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

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。文章中也有算法计算作业数量的引用，但你只需要尝试列出两个作业，这可能会更有效率。