我有一个 bool 公式:(x_ {1}或x_ {2})和(x_ {3}或x_ {4})和.....和(x_ {2r-1}或x_ {2r}) ，其中 x_ {i} 属于集合: {p_ {1}，p_ {2}，... p_ {99}，〜p_ {1}，〜p_ {2}，...〜 p_ {99}} ，我必须确定给定公式对于 x_ {i} 的某些值是否正确。
我知道这通常在计算上很困难。但是，有什么相当快速的方法可以解决这个特定问题？到目前为止，我已经尝试过回溯-递归地，我为每个可能的变量赋予每个可能的值(0或1，所以数量不多)，而每个尚未获得值(value)的变量都是微不足道的。在深入研究递归之前，我先检查了公式(即使不是每个变量都有一个值)，如果它为假，我也不会深入研究。但这太慢了。有任何想法吗？我将非常感谢您的帮助。
最佳答案
如果每个OR子句只有两个变量，那么您就有了2-SAT，它具有线性时间解。