2可满足性问题，无论是独一无二的真值赋值存在与否

Question

我有个问题，就是2-SAT问题的扩展。在标准的2-SAT问题，我们可以发现任何真理分配这取决于我们选择顶点的顺序的。我要检查是否存在一个且只有一个真理分配（即只有一个组合）该表达式是可满足的。文字的数量可以设为100000。 一种方法是找出所有可能的真值赋值，然后对它们进行比较，如果它们是不同的。但问题是，每次比较，我会比较十万值（无文字的）。有没有什么有效的方法？

Answer 1

菲德（1994）描述了一种算法用于高效地列出所有解决方案，以一个给定的2-可满足实例的。也有文章的算法来计算分配的数量，引文，但你只需要尝试上市两项工作，这可能是更有效的。