生成无法满足的测试问题
Generating unsatisfiable test problems
我正在尝试生成一些命题可满足性的测试问题，特别是生成一些不可满足的问题，但是根据固定的模式，这样对于任何 N，都可以生成 N 个变量的不可满足问题。
一个简单的解决方案是 x1、x1=>x2、x2=>x3 ... !xN 除了这将是所有单元子句，任何 SAT 求解器都可以立即处理, 所以这不是一个足够严格的测试。
N 个变量的不可满足问题的模式是什么，这些问题不是随机的，通过检查可以看出是不可满足的，但至少对于 SAT 求解器来说是不平凡的？
想到的第一个例子是对包含每个变量的所有可能析取取一次合取。例如，如果您的变量是 p1、p2 和 p3：
(¬p1 ∨ ¬p2 ∨ ¬p3) ∧ (¬p1 ∨ ¬p2 ∨ p3) ∧ (¬p1 ∨ p2 ∨ ¬p3) ∧ (¬p1 ∨ p2 ∨ p3) ∧ (p1 ∨ ¬p2 ∨ ¬p3) ∧ (p1 ∨ ¬p2 ∨ p3) ∧ (p1 ∨ p2 ∨ ¬p3) ∧ (p1 ∨ p2 ∨ p3)
另一种描述方式是：每个可能赋值的否定的合取。例如，¬(p1 ∧ p2 ∧ p3) = (¬p1 ∨ ¬p2 ∨ ¬p3) 是公式的子句。因此，每一种可能的赋值都不能恰好满足一个子句。然而，我们只知道这一点，因为我们验证了这些条款是详尽无遗的。
如果我们尝试转换为规范的析取范式，无论我们以何种顺序尝试变量，我们都无法更快地完成，最终我们得到：
(p1 ∧ ¬p1 ∧ p2 ∧ p3) ∨ (p1 ∧ p2 ∧ ¬p2 ∧ p3) ∨ (p1 ∧ p2 ∧ p3 ∧ ¬p3)
我们生成的每个子句都无法满足，但只有在展开所有子句时才会看到这一点。如果我们试图寻找一个令人满意的赋值，不管我们以什么顺序尝试变量，我们只能在指数时间内穷尽地测试每一个可能的赋值。
可能有一个 SAT-solver 可以测试这种特殊情况，尽管测试每个可能的子句都在输入中本身会花费指数时间，并且将任意输入放入规范形式有效地说，三个变量只有八个可能的子句，我们已经检查过没有重复项，这也需要一段时间。
Pigeonhole problems are non-trivial for CDCL-based SAT solvers without preprocessing, i.e. see Detecting Cardinality Constraints in CNF. The paper Hard Examples for Resolution 您可能会感兴趣。
我正在尝试生成一些命题可满足性的测试问题，特别是生成一些不可满足的问题，但是根据固定的模式，这样对于任何 N，都可以生成 N 个变量的不可满足问题。
一个简单的解决方案是 x1、x1=>x2、x2=>x3 ... !xN 除了这将是所有单元子句，任何 SAT 求解器都可以立即处理, 所以这不是一个足够严格的测试。
N 个变量的不可满足问题的模式是什么，这些问题不是随机的，通过检查可以看出是不可满足的，但至少对于 SAT 求解器来说是不平凡的？
想到的第一个例子是对包含每个变量的所有可能析取取一次合取。例如，如果您的变量是 p1、p2 和 p3：
(¬p1 ∨ ¬p2 ∨ ¬p3) ∧ (¬p1 ∨ ¬p2 ∨ p3) ∧ (¬p1 ∨ p2 ∨ ¬p3) ∧ (¬p1 ∨ p2 ∨ p3) ∧ (p1 ∨ ¬p2 ∨ ¬p3) ∧ (p1 ∨ ¬p2 ∨ p3) ∧ (p1 ∨ p2 ∨ ¬p3) ∧ (p1 ∨ p2 ∨ p3)
另一种描述方式是：每个可能赋值的否定的合取。例如，¬(p1 ∧ p2 ∧ p3) = (¬p1 ∨ ¬p2 ∨ ¬p3) 是公式的子句。因此，每一种可能的赋值都不能恰好满足一个子句。然而，我们只知道这一点，因为我们验证了这些条款是详尽无遗的。
如果我们尝试转换为规范的析取范式，无论我们以何种顺序尝试变量，我们都无法更快地完成，最终我们得到：
(p1 ∧ ¬p1 ∧ p2 ∧ p3) ∨ (p1 ∧ p2 ∧ ¬p2 ∧ p3) ∨ (p1 ∧ p2 ∧ p3 ∧ ¬p3)
我们生成的每个子句都无法满足，但只有在展开所有子句时才会看到这一点。如果我们试图寻找一个令人满意的赋值，不管我们以什么顺序尝试变量，我们只能在指数时间内穷尽地测试每一个可能的赋值。
可能有一个 SAT-solver 可以测试这种特殊情况，尽管测试每个可能的子句都在输入中本身会花费指数时间，并且将任意输入放入规范形式有效地说，三个变量只有八个可能的子句，我们已经检查过没有重复项，这也需要一段时间。
Pigeonhole problems are non-trivial for CDCL-based SAT solvers without preprocessing, i.e. see Detecting Cardinality Constraints in CNF. The paper Hard Examples for Resolution 您可能会感兴趣。