假设有一个可满足性问题（称为 oscillating-CNF），其中输入是 CNF 子句的串列，我们想要证明这个问题确实是 NP 完全的（通过将 CNF-SAT 简化为 oscillating-CNF）。当每个偶数索引子句 (0-2-4) 为真且每个非偶数索引子句为假 (1-3-5...) 时，一个令人满意的振荡 CNF 实体。

我的问题是，这是一个可行的策略：

1. 从 CNF 中选择一个随机变量（称为 R1）
2. 否定 CNF 表达式
3. 将步骤 2 中的否定表达式转换回 CNF 格式
4. 创建一个串列并在每个偶数索引位置 (R1 || !R1)，并在奇数索引中放置步骤 3 中的子句。
5. 将此串列用作振荡 CNF 问题的输入

uj5u.com热心网友回复：

问题是，当你否定一个析取从句时，它变成了一个连词。我会将原始问题保留在偶数子句中，并为奇数子句引入辅助变量（在不包含原始变量的情况下使它们无法满足）。