2-可满足性问题中的实现问题

Question

我想实现 100000 个文字的 2-SAT 问题。所以会有 200000 个顶点。所以我坚持拥有每个顶点的所有可到达顶点的数组，空间复杂度为 O(200000^2) 这是不可行的，所以请为此提出一个解决方案。请阐明 2-SAT 问题的有效实施。

Answer 1

从 维基百科:

...2-可满足性可以在多项式时间内求解。作为 阿斯普瓦尔、普拉斯和塔里扬 (1979) 观察到，2-可满足性实例是可解的，当且仅当实例的每个变量属于蕴涵图的不同强连通分量而不是同一变量的否定。由于可以通过基于深度优先搜索的算法在线性时间内找到强连通分量，因此相同的线性时间界限也适用于 2-可满足性。

我不会假装理解该段的大部分内容，但看起来 是 一种可用于解决 2-SAT 问题的算法，该算法在该参考文档中进行了描述（用于测试某些量化布尔公式的真实性的线性时间算法）。它显然可以在网上以大约 20 美元的价格购买。我不确定这是否有帮助，但确实如此！

更新： 可以找到同一文档的免费 PDF 这里. 。信用去往 利奥里 为了找到。

Answer 2

整个线索有点混乱。是的，人们可以在线性时间内求解 2-sat，但不行——你无法求解那么多变量。求解 2-sat 的时间与蕴涵数成线性关系，对于 200 000 个变量，其可能达到 (200000*199999)/2，此外，如果您使用此解决方案，您将需要大约相同数量的内存。还有另一种解决方案（不使用速度较慢但不需要那么多内存的强连接组件）。