我有兴趣了解已知为多项式（或更实际地，O(N^2)）的布尔可满足性问题的特殊情况。这些案例还应该有有效的算法来实际生成所有令人满意的实例，其中高效我的意思是需要 O(N #SAT) 来生成所有实例的序列。第二个条件可能暗示第一个条件，但我不清楚。
简单的例子：1SAT :)
简单的例子：带有“链”子句的 2SAT，因此用子句连接变量的图是一条线。
有更多的地方吗？谢谢。
问问题
142 次
1 回答
3
来自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 实例属于前五个类别之一。
于 2012-01-04T02:08:58.223 回答