Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

Abstract

In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $\ddot{I}†$ 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 $\ddot{I}†$ throughout the transformation. In this paper, we demonstrate that the optimal approximation factor for Maxmin E$k$-SAT Reconfiguration is $1-\hat{I}˜\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\ge 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Ã¥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.

To appear in Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025)