标题： 渐近最优的E$k$-SAT重配置不可近似性 显示英文标题

标题： Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

摘要： 在Maxmin E$k$-SAT重配置问题中，我们给定一个可满足的$k$-CNF公式$\varphi$，其中每个子句恰好包含$k$个文字，并且给定其一个满足赋值对。目标是在变换过程中反复翻转单个变量的值，将一个满足赋值转换为另一个，同时最大化在整个变换过程中满足子句的最小比例$\varphi$。在本文中，我们证明了Maxmin E$k$-SAT重配置问题的最优近似因子为$1 - \Theta\left(\frac{1}{k}\right)$。 在算法方面，我们为每个$k \geq 3$开发了一个确定性的$\left(1-\frac{1}{k-1}-\frac{1}{k}\right)$-因子近似算法。 在难度方面，我们证明了对于每个足够大的$k$，在$1-\frac{1}{10k}$的因子范围内近似这个问题是$\mathsf{PSPACE}$-难的。 注意到 Maxmin E$k$-SAT Reconfiguration 的$\mathsf{NP}$类似物是 Max E$k$-SAT，其近似阈值为$1-\frac{1}{2^k}$，由 Håstad（JACM 2001）证明。据我们所知，这是第一个近似阈值（渐近意义上）比其$\mathsf{NP}$类似物更差的重配置问题。为了证明困难性结果，我们引入了一种新的“非单调”测试，该测试专门针对重配置问题，尽管在 PCP 范式中并不有用。 显示英文摘要

摘要： In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $\varphi$ where each clause contains exactly $k$ literals, along with a pair of its satisfying assignments. The objective is transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing the minimum fraction of satisfied clauses of $\varphi$ throughout the transformation. In this paper, we demonstrate that the optimal approximation factor for Maxmin E$k$-SAT Reconfiguration is $1 - \Theta\left(\frac{1}{k}\right)$. On the algorithmic side, we develop a deterministic $\left(1-\frac{1}{k-1}-\frac{1}{k}\right)$-factor approximation algorithm for every $k \geq 3$. On the hardness side, we show that it is $\mathsf{PSPACE}$-hard to approximate this problem within a factor of $1-\frac{1}{10k}$ for every sufficiently large $k$. Note that an ``$\mathsf{NP}$ analogue'' of Maxmin E$k$-SAT Reconfiguration is Max E$k$-SAT, whose approximation threshold is $1-\frac{1}{2^k}$ shown by H\r{a}stad (JACM 2001). To the best of our knowledge, this is the first reconfiguration problem whose approximation threshold is (asymptotically) worse than that of its $\mathsf{NP}$ analogue. To prove the hardness result, we introduce a new ``non-monotone'' test, which is specially tailored to reconfiguration problems, despite not being helpful in the PCP regime.