{"ID":2887761,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.00276","arxiv_id":"2508.00276","title":"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 $\\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 - Θ\\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å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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2508.00276","url_pdf":"https://arxiv.org/pdf/2508.00276v1","authors":"[\"Shuichi Hirahara\",\"Naoto Ohsaka\"]","published":"2025-08-01T02:52:12Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}