我有一个 bool 公式:(x_{1} or x_{2}) and (x_{3} or x_{4}) and ..... and (x_{2r-1} or x_{2r})，其中 x_{i} 属于集合:{p_{1}, p_{2}, ... p_{99} , ~ p_{1}, ~p_{2}, ... ~p_{99} } 并且我必须确定对于 x_{i} 的某些值，给定的公式是否为真.
我知道这通常在计算上很困难。但是有什么非常快速的方法可以解决这个特定问题吗？到目前为止，我已经尝试过回溯——在递归中，我用每个可能的变量和每个可能的值(0 或 1，所以不多)代替每个可能的值，每个变量，还没有得到值(value)，是微不足道的。在我深入递归之前，我会检查公式(即使不是每个变量都有一个值)，如果它是假的，我就不会深入。但它太慢了。有任何想法吗？如果您能提供帮助，我将不胜感激。
最佳答案
如果每个 OR 子句只有两个变量，那么你有 2-SAT ，它有一个线性时间的解决方案。
关于algorithm - bool 可满足性 - 算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11364716/