NAE-SAT 的一份简单调研

Important

这份调研阅读了很多份论文，这里会使用一个 biblatex 来给出引用，调研有一份 Typst 版，可以参考

NAE-SAT

Definition

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

Definition 1：对于一个给定的 CNF 公式 $c_1\wedge \cdots \wedge c_m$，其中 $c_i={\bigvee }_j^t{x}_t$ 且 $t\ge 1,t\in \mathbb{Z}$，是否存在一组赋值 $\varphi =(x_1,\dots ,x_n),x_i\in \{0,1\}$，使得 CNF 成真

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

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

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

在文章 (Porschen et al., n.d.) 中， 其提及了两个典型的问题：

• Set Splitting, 见 Set Splitting

• Hypergraph bicolorability，见 Hypergraph bicolorability

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

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

Set Splitting

Cite

In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson’s classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability.

— WikiPedia

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

给定子集簇 $\mathcal{F}=\{S_1,S_2,S_3,\dots ,S_n\}$，全集为 $S$， 满足 $\forall S_i\in \mathcal{F},S_i\subseteq S$，问是否存在两个集合 $X_1,X_2$ 满足：

$$\begin{array}{rl}\forall S_i\in \mathcal{F},& \neg (S_i\subseteq X_1)\wedge \neg (S_i\subseteq X_2)\\ & X_1\cap X_2=\varnothing ,X_1\cup X_2=S\end{array}$$

我们考虑以下朴素编码：

簇中的每个子集本质上就是一个子句，我们对全集 $S$ 中的每个元素进行编号：$x_1,x_2,\dots ,x_m$，于是，$\mathcal{F}={\bigwedge }_{i=1}^n({\bigvee }_{x_j\in S_i}{x}_j)$

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

Hypergraph bicolorability

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

显然 Set Splitting 中对于子集簇 $\mathcal{F}$ 与全集 $S$ 可以直接对应到超图 $\mathcal{H}=<V,E>\leftrightarrow <S,\mathcal{F}>$

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

Others

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

• NAE-SAT 的应用场景少

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

在 (El-Kadi and Bondesan 2024) 中提到，NAE-SAT 在计算复杂性的规约上有着重要的作用，

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

NAE-k-SAT / k-NAE-SAT

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

Theory

在这个问题上的理论研究显然比一般的 NAE-SAT 要多，例如 (Ding, Sly, and Sun 2013), (Sly and Sohn 2023), (Nam, Sly, and Sohn 2023), (Gamarnik and Sudan 2017) 等，

然而，在这些文章之中，(Ding, Sly, and Sun 2013) 更集中于探讨 random d-regular k-NAE-SAT；

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

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

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

(Ding, Sly, and Sun 2013) 的工作明确建立了一个阈值 $d_{\ast }\equiv d_{\ast }(k)$，并证明，当 $d<d_{\ast }$ 时，随机生成的 CNF 几乎总是可满足的；而当 $d>d_{\ast }$ 时，随机生成的 CNF 几乎总是不可满足的。如果阈值 $d_{\ast }$ 恰好为整数，我们表明该问题是可满足的，且其概率远离 0 和 1。

Non-Theory

(El-Kadi and Bondesan 2024)是为数不多的非理论的工作，farhiQuantumApproximateOptimization2014(Farhi, Goldstone, and Gutmann 2014) 在最大割问题中早有应用，论文中举例用的就是最大割问题，此问题在 MAX CUT 中介绍。

然而，(El-Kadi and Bondesan 2024) 也并未提及 k-NAE-SAT 的实际应用。

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

最后，文章将 QAOA 与传统算法 WalkSATlm(Cai, Luo, and Su 2015) 与魔改 WalkSATlm 得到的 WalkSATm2b2，如下图所示，进行对比（在这里只对比了中位运行时间）：

使用的实例为随机生成的 $k\in \{3,\dots ,10\}$ 的 $2500$ 个随机生成的 NAE-SAT 实例(保证了一定有解)。

MAX NAE-SAT

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

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

MAX CUT

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

Definition 6： 给定一个无向图 $G=(V,E)$，找到一个顶点集合的划分 $(S,\overline{S})$，使得划分在连接 $S$ 与 $\overline{S}$ 的边的数量最大化

这个问题可以认为是 MAX k-NAE-SAT 的一个特例，即 MAX 2-NAE-SAT：其中， $V$ 为全集 $S$，$E$ 为子集簇 $\mathcal{F}$。

对于最大割问题的近似算法，在 (O’Donnell and Wu 2008), (Goemans and Williamson 1995) 中均有介绍，而如果我们为边设置权重，就能得到 weighted-MAX-CUT 问题。

MAX Set Splitting

对于 $k\ge 3$ 的情况，根据 Set Splitting 中，我们也可以为子集簇$\mathcal{F}$ 中的每个子集设置权重，这样就得到了问题 MAX Set Splitting，在 (Zhang, Ye, and Han 2004), (Andersson and Engebretsen, n.d.) 中均有介绍，但工作均为求出近似比 $\alpha$，与 MAX CUT 中提及的文章工作类似。

MAX k-NAE-SAT

在理论方面，(Brakensiek et al. 2024) 的工作主要是确定了 $k\ge 3$ 中，算法的最优近似比，见下表：

References

Andersson, Gunnar, and Lars Engebretsen. n.d. “Better Approximation Algorithms for SET SPLITTING NOT-ALL-EQUALSAT.”

Brakensiek, Joshua, Neng Huang, Aaron Potechin, and Uri Zwick. 2024. “On the Mysteries of MAX NAE-SAT.” September 26, 2024. http://arxiv.org/abs/2009.10677.

Cai, Shaowei, Chuan Luo, and Kaile Su. 2015. “Improving WalkSAT By Effective Tie-Breaking and Efficient Implementation.” The Computer Journal 58 (11): 2864–75. https://doi.org/10.1093/comjnl/bxu135.

Ding, Jian, Allan Sly, and Nike Sun. 2013. “Satisfiability Threshold for Random Regular NAE-SAT.” October 17, 2013. http://arxiv.org/abs/1310.4784.

El-Kadi, Andrew, and Roberto Bondesan. 2024. “Quantum Approximate Optimisation for Not-All-Equal SAT.” January 5, 2024. http://arxiv.org/abs/2401.02852.

Farhi, Edward, Jeffrey Goldstone, and Sam Gutmann. 2014. “A Quantum Approximate Optimization Algorithm.” November 14, 2014. http://arxiv.org/abs/1411.4028.

Gamarnik, David, and Madhu Sudan. 2017. “Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem.” SIAM Journal on Computing 46 (2): 590–619. https://doi.org/10.1137/140989728.

Goemans, Michel X., and David P. Williamson. 1995. “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.” Journal of the ACM 42 (6): 1115–45. https://doi.org/10.1145/227683.227684.

Nam, Danny, Allan Sly, and Youngtak Sohn. 2023. “One-Step Replica Symmetry Breaking of Random Regular NAE-SAT I.” December 13, 2023. http://arxiv.org/abs/2011.14270.

O’Donnell, Ryan, and Yi Wu. 2008. “An Optimal Sdp Algorithm for Max-Cut, and Equally Optimal Long Code Tests.” In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 335–44. Victoria British Columbia Canada: ACM. https://doi.org/10.1145/1374376.1374425.

Porschen, Stefan, Tatjana Schmidt, Ewald Speckenmeyer, and Andreas Wotzlaw. n.d. “XSAT and NAE-SAT of Linear CNF classesI.”

Sly, Allan, and Youngtak Sohn. 2023. “Local Geometry of NAE-SAT Solutions in the Condensation Regime.” July 30, 2023. http://arxiv.org/abs/2305.17334.

Zhang, Jiawei, Yinyu Ye, and Qiaoming Han. 2004. “Improved Approximations for Max Set Splitting and Max NAE SAT.” Discrete Applied Mathematics 142 (1–3): 133–49. https://doi.org/10.1016/j.dam.2002.07.001.