NAE-SAT#

Definition#

首先，我们重申 SAT 的定义：

Definition 1：对于一个给定的 CNF 公式 ，其中 且 ，是否存在一组赋值 ，使得 CNF 成真

而 NAE-SAT，全称 Not-All-Equal SAT，就是在 SAT 的基础上再加上一条约束：

Definition 2：给定一个 SAT 问题，要求每个子句 中至少有一个文字为真且至少有一个文字为假 （也就是说一个子句中不可能所有变量均相等）

注意到，NAE-SAT 是对称的，即，我们翻转赋值 中的每个赋值后得到 ， 仍然是问题的一个成真赋值。

在文章 [@porschenXSATNAESATLinear] 中， 其提及了两个典型的问题：

• Set Splitting, 见 #Set Splitting

• Hypergraph bicolorability，见 #Hypergraph bicolorability

并且，文章 [@porschenXSATNAESATLinear] 在 Concluding Remarks and Open Problems 一节中提出： 对于 NAE-SAT，到目前为止还没有取得这样的进展(指精确算法的提出与优化)，这并不奇怪，因为对于不受限制的情况，NAE-SAT 与 SAT 本身一样难。 因此，我们面临的问题是，是否可以提供精确的确定性算法来解决 NAE-SAT。

当然，这已经是 2011 年提出的 Open Problem 了，但似乎到今年（2024）为止，还没有论文提出精确算法来求解 NAE-SAT

Set Splitting#

此问题可以轻易编码为 NAE-SAT：

给定子集簇 ，全集为 ， 满足 ，问是否存在两个集合 满足：

\begin{aligned}
\forall S_i \in \mathcal{F},& \neg (S_i \subseteq X_1) \wedge \neg (S_i \subseteq X_2)\\
& X_1 \cap X_2 = \emptyset, X_1 \cup X_2 = S
\end{aligned}

我们考虑以下朴素编码：

簇中的每个子集本质上就是一个子句，我们对全集 中的每个元素进行编号：，于是，

最后我们得到赋值为 ，赋值为真的变量为集合 中的元素，否则为 中的元素

Hypergraph bicolorability#

超图（Hypergraph）: 一种广义的图，其中边（称为超边）可以连接任意数量的顶点，而不仅仅是两个顶点。

显然 #Set Splitting 中对于子集簇 与全集 可以直接对应到超图

于是，问题可以变为一个 2-color 问题，即只用两种颜色如何将超图完全着色。

Others#

暂时未找到 NAE-SAT 的进展，目前可能原因在于：

• NAE-SAT 的应用场景少

业内（但本文引用的大多数论文都是 Math 与 Physics 分类的，CS 分类也是 TCS），大多数的研究都集中在 NAE-SAT 的两个变种上，我们将在 #NAE-k-SAT / k-NAE-SAT, #MAX NAE-SAT 中介绍。

在 [@el-kadiQuantumApproximateOptimisation2024] 中提到，NAE-SAT 在计算复杂性的规约上有着重要的作用，

这或许也能解释，为什么关于 NAE-SAT 的均是理论研究。

NAE-k-SAT / k-NAE-SAT#

Definition 3：给定一个 SAT 问题，要求每个子句 中至少有一个文字为真且至少有一个文字为假，并且每个子句中恰好有 个文字

Theory#

在这个问题上的理论研究显然比一般的 NAE-SAT 要多，例如 [@dingSatisfiabilityThresholdRandom2013], [@slyLocalGeometryNAESAT2023], [@namOnestepReplicaSymmetry2023], [@gamarnikPerformanceSequentialLocal2017] 等，

然而，在这些文章之中，[@dingSatisfiabilityThresholdRandom2013] 更集中于探讨 random d-regular k-NAE-SAT；

而 [@slyLocalGeometryNAESAT2023], [@namOnestepReplicaSymmetry2023] 更集中于讨论 random d-regular k-NAE-SAT 在物理学中的应用（毕竟作者是 Allan Sly，这是因为 random k-NAE-SAT 在稀疏随机约束求解问题中是最简单的一类了，统计物理学中将这种问题描述为 replica symmetry breaking。然而，这些文章其实都看不懂，没有物理学的知识导致我不知道这些理论有什么用

首先，我们介绍什么是 random d-regular k-NAE-SAT：

Definition 4： 给定一个随机生成的 CNF，其包含了 条子句，且每条子句的长度都为 ，是否存在一组赋值 使得每条子句中的文字不全为真

[@dingSatisfiabilityThresholdRandom2013] 的工作明确建立了一个阈值 ，并证明，当 时，随机生成的 CNF 几乎总是可满足的；而当 时，随机生成的 CNF 几乎总是不可满足的。如果阈值 恰好为整数，我们表明该问题是可满足的，且其概率远离 0 和 1。

Non-Theory#

[@el-kadiQuantumApproximateOptimisation2024 ]是为数不多的非理论的工作，farhiQuantumApproximateOptimization2014[@farhiQuantumApproximateOptimization2014] 在最大割问题中早有应用，论文中举例用的就是最大割问题，此问题在 #MAX CUT 中介绍。

然而，[@el-kadiQuantumApproximateOptimisation2024] 也并未提及 k-NAE-SAT 的实际应用。

由于 QAOA 算法 本质上是一个近似优化算法，因此没办法保证一定获得最优解，于是，衡量 QAOA 的效果是通过成功率(success ratio)的，如下图所示：

最后，文章将 QAOA 与传统算法 WalkSATlm[@caiImprovingWalkSATEffective2015] 与魔改 WalkSATlm 得到的 WalkSATm2b2，如下图所示，进行对比（在这里只对比了中位运行时间）：

使用的实例为随机生成的 的 个随机生成的 NAE-SAT 实例(保证了一定有解)。

MAX NAE-SAT#

Definition 5： 给定一个 CNF，要求每个子句 中至少有一个文字为真且至少有一个文字为假，目标是找到一组赋值 ，使得满足条件的子句数量最大化

MAX NAE-SAT 及其变种 MAX k-NAE-SAT（此变种问题不再给定义）的工作相较于前两个问题会较多。

MAX CUT#

Max Cut，最大割问题，其定义如下：

Definition 6： 给定一个无向图 ，找到一个顶点集合的划分 ，使得划分在连接 与 的边的数量最大化

这个问题可以认为是 MAX k-NAE-SAT 的一个特例，即 MAX 2-NAE-SAT：其中， 为全集 ， 为子集簇 。

对于最大割问题的近似算法，在 [@odonnellOptimalSdpAlgorithm2008], [@goemansImprovedApproximationAlgorithms1995] 中均有介绍，而如果我们为边设置权重，就能得到 weighted-MAX-CUT 问题。

MAX Set Splitting#

对于 的情况，根据 #Set Splitting 中，我们也可以为子集簇 中的每个子集设置权重，这样就得到了问题 MAX Set Splitting，在 [@zhangImprovedApproximationsMax2004], [@anderssonBetterApproximationAlgorithms] 中均有介绍，但工作均为求出近似比 ，与 #MAX CUT 中提及的文章工作类似。

MAX k-NAE-SAT#

在理论方面，[@brakensiekMysteriesMAXNAESAT2024] 的工作主要是确定了 中，算法的最优近似比，见下表：

References#

[^ref]