Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration

Abstract

In the Maxmin $q$-CSP Reconfiguration problem, given a satisfiable $q$-CSP instance and a pair of its satisfying assignments, we are asked to transform one assignment into the other by repeatedly changing the value assigned to a single variable. The objective is to find such a transformation that maximizes the minimum fraction of satisfied constraints along the transformation. In this paper, we prove that for any $q\ge 2$ and $\epsilon >0$, Maxmin $q$-CSP Reconfiguration is $\mathsf{PSPACE}$-hard to approximate within a factor of $\frac{1}{2^{q-1}}+\epsilon$. To complement this hardness result, we prove that a $(\frac{1}{2^{q-1}}-\epsilon )$-factor approximation for Maxmin $q$-CSP Reconfiguration is in $\mathsf{NP}$ in the perfect completeness case. These results establish the optimal $\mathsf{PSPACE}$-hardness of approximating Maxmin $q$-CSP Reconfiguration for every $q\ge 2$ under $\mathsf{NP}\ne \mathsf{PSPACE}$.

79 pages, to appear in Proceedings of the 67th IEEE Symposium on Foundations of Computer Science (FOCS 2026)

Topics & keywords