SAT和特殊的#SAT的特殊情况，其复杂度最高为O（n ^ 2），并且具有生成实例的有效算法？

Question

我对了解布尔可满足性问题的特殊情况感兴趣，这些情况已知是多项式的（或更实际的是O（N ^ 2））。这些情况还应该具有用于实际生成所有令人满意的实例的有效算法，其中高效是指需要O（N #SAT）来生成所有实例的序列。第二个条件可能暗示第一个条件，但我不清楚。

典型例子：1SAT：）

示例：2SAT具有子句的“链”，因此将带有子句的变量连接的图形是一条线。

在某处还有更多列表吗？谢谢。

Answer 1

来自 Schaefer的满意度问题的复杂性：

我们证明（假设P！= NP）SAT（S）仅在满足以下至少一项条件的情况下才能确定多项式时间：

（a）当所有变量均为0时，满足S中的每个关系。

（b）当所有变量均为1时，满足S中的每个关系。

（c）S中的每个关系都可以通过CNF公式来定义，其中每个合词最多具有一个否定变量。

（d）S中的每个关系都可以通过CNF公式定义，其中每个合词最多具有一个非负变量。

（e）S中的每个关系都可以由一个CNF公式定义，该CNF公式在每个合词中最多包含2个文字。

（f）S中的每个关系都是在两个元素字段{0,1}上的线性方程组的解的集合。

前两个是可解的O（1），后三个是O（n），最后一个是O（n ^ 3）（我认为）。因此，您想要的SAT实例在前五个类之一中。