标题： 局部枚举：非全等情形 显示英文标题

标题： Local Enumeration: The Not-All-Equal Case

摘要： Gurumukhani 等人（CCC'24）提出了局部枚举问题 Enum(k, t) 作为一种突破超级强指数时间假设（SSETH）的方法：对于自然数$k$和参数$t$，给定一个$n$变量的$k$-CNF，且没有汉明权重小于$t(n)$的满足赋值，枚举所有汉明权重恰好为$t(n)$的满足赋值。 此外，他们为 Enum(k, t) 提供了一个随机算法，并采用新思路分析了第一个非平凡的情况，即$k = 3$。 特别是，他们在期望时间$1.598^n$内解决了 Enum(3, n/2)。 一个简单的构造表明了一个下界为 $6^{\frac{n}{4}} \approx 1.565^n$。 在本文中，我们表明，要打破SSETH，只需考虑一个更简单的局部枚举问题NAE-Enum(k, t)：对于自然数$k$和参数$t$，给定一个$n$元$k$-CNF，其没有汉明重量小于$t(n)$的满足赋值，枚举所有汉明重量恰好为$t(n)$的非全等（NAE）解，即每个子句中至少有一个文字被满足且至少有一个文字被否定的解。我们改进了Gurumukhani等人提出的算法，并证明该算法最优地解决了NAE-Enum(3, n/2)，即在期望时间$poly(n) \cdot 6^{\frac{n}{4}}$内完成。 显示英文摘要

摘要： Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no satisfying assignment of Hamming weight less than $t(n)$, enumerate all satisfying assignments of Hamming weight exactly $t(n)$. Furthermore, they gave a randomized algorithm for Enum(k, t) and employed new ideas to analyze the first non-trivial case, namely $k = 3$. In particular, they solved Enum(3, n/2) in expected $1.598^n$ time. A simple construction shows a lower bound of $6^{\frac{n}{4}} \approx 1.565^n$. In this paper, we show that to break SSETH, it is sufficient to consider a simpler local enumeration problem NAE-Enum(k, t): for a natural number $k$ and a parameter $t$, given an $n$-variate $k$-CNF with no satisfying assignment of Hamming weight less than $t(n)$, enumerate all Not-All-Equal (NAE) solutions of Hamming weight exactly $t(n)$, i.e., those that satisfy and falsify some literal in every clause. We refine the algorithm of Gurumukhani et al. and show that it optimally solves NAE-Enum(3, n/2), namely, in expected time $poly(n) \cdot 6^{\frac{n}{4}}$.