Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913969473585152 |
|---|---|
| author | Hirahara, Shuichi Ohsaka, Naoto |
| author_facet | Hirahara, Shuichi Ohsaka, Naoto |
| contents | In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $φ$ 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 $φ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_00276 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration Hirahara, Shuichi Ohsaka, Naoto Computational Complexity Discrete Mathematics Data Structures and Algorithms In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $φ$ 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 $φ$ 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. |
| title | Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.00276 |