我有兴趣学习已知是多项式的布尔可满足性问题的特殊情况(或者更现实地说，O(N^2))。这些情况还应该有一个有效的算法来生成所有令人满意的实例，这里的有效是指生成所有实例的序列需要0 (n# SAT)。第二个条件可能暗示了第一个条件，但我不清楚。
小例子:1SAT:)
小例子:2SAT用"链"子句，使得用子句连接变量的图是一条线。
是否有更多的列表?谢谢。
摘自Schaefer的《可满足性问题的复杂性》:
我们证明(假设p != NP) SAT(S)是多项式时间可决定的，仅当至少满足以下条件之一:
(a)当所有变量为0时，S中的所有关系都满足。
(b)当所有变量为1时，S中的所有关系都满足。
(c) S中的每个关系都可以用一个CNF公式定义，其中每个连接至多有一个负变量。
(d) S中的每个关系都可以用一个CNF公式定义，其中每个连接最多有一个非负变量。
(e) S中的每个关系由一个CNF公式定义，每个连接词最多有2个字面值。
(f) S中的每一个关系是二元域{0,1}上线性方程组的解的集合。
前两个是可解的O(1)，后三个是O(n)最后一个是O(n^3)(我想)。所以你想要的SAT实例在前五个类中的一个