将 CNF-SAT 减少到这个问题的策略
Strategy for reducing CNF-SAT to this problem
假设存在一个可满足性问题（称之为 oscillating-CNF），其中输入是 CNF 子句的列表，我们想证明这个问题确实是 NP 完全的（通过将 CNF-SAT 简化为 oscillating-CNF ).一个令人满意的振荡 CNF 实例是每个偶数索引子句 (0-2-4) 为真且每个不均匀索引子句为假 (1-3-5...)。
我的问题是：
- 从 CNF 中选择一个随机变量（称之为 R1）
- 否定 CNF 表达式
- 将步骤 2 中的否定表达式转换回 CNF 格式
- 创建一个列表，在每个偶数索引位置 (R1 || !R1)，在奇数索引位置放置步骤 3 中的子句。
- 使用此列表作为振荡 CNF 问题的输入
问题是，当你否定一个析取从句时，它变成了一个连词。我会在偶数子句中保留原始问题，并为奇数子句引入辅助变量（使它们在不包含原始变量的情况下变得平凡不可满足）。
假设存在一个可满足性问题（称之为 oscillating-CNF），其中输入是 CNF 子句的列表，我们想证明这个问题确实是 NP 完全的（通过将 CNF-SAT 简化为 oscillating-CNF ).一个令人满意的振荡 CNF 实例是每个偶数索引子句 (0-2-4) 为真且每个不均匀索引子句为假 (1-3-5...)。
我的问题是：
- 从 CNF 中选择一个随机变量（称之为 R1）
- 否定 CNF 表达式
- 将步骤 2 中的否定表达式转换回 CNF 格式
- 创建一个列表，在每个偶数索引位置 (R1 || !R1)，在奇数索引位置放置步骤 3 中的子句。
- 使用此列表作为振荡 CNF 问题的输入
问题是，当你否定一个析取从句时，它变成了一个连词。我会在偶数子句中保留原始问题，并为奇数子句引入辅助变量（使它们在不包含原始变量的情况下变得平凡不可满足）。