我有一个布尔公式：（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 所以不多）替换为每个可能的变量，并且每个尚未获得值的变量都是微不足道的。在我深入研究递归之前，我会选择公式（即使不是每个变量都有一个值），如果它是假的，我就不会更深入。但它太慢了。有什么想法吗？我将非常感谢您的帮助。
如果每个 OR 子句只有两个变量，则有 2-SAT，它具有线性时间解。