  The field of combinatorial reconfiguration studies search problems with a
focus on transforming one feasible solution into another. Recently, Ohsaka
[STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH),
which roughly asserts that for some $\epsilon>0$, given as input a $k$-CSP
instance (for some constant $k$) over some constant sized alphabet, and two
satisfying assignments $\psi_s$ and $\psi_t$, it is PSPACE-hard to find a
sequence of assignments starting from $\psi_s$ and ending at $\psi_t$ such that
every assignment in the sequence satisfies at least $(1-\epsilon)$ fraction of
the constraints and also that every assignment in the sequence is obtained by
changing its immediately preceding assignment (in the sequence) on exactly one
variable. Assuming RIH, many important reconfiguration problems have been shown
to be PSPACE-hard to approximate by Ohsaka [STACS'23; SODA'24].
  In this paper, we prove RIH and establish the first (constant factor)
PSPACE-hardness of approximation results for many reconfiguration problems,
resolving an open question posed by Ito et al. [TCS'11]. Our proof uses known
constructions of Probabilistically Checkable Proofs of Proximity (in a
black-box manner) to create the gap. Independently, Hirahara and Ohsaka
[STOC'24] have also proved RIH.
  We also prove that the aforementioned $k$-CSP Reconfiguration problem is
NP-hard to approximate to within a factor of $1/2 + \epsilon$ (for any
$\epsilon>0$) when $k=2$. We complement this with a $(1/2 -
\epsilon)$-approximation polynomial time algorithm, which improves upon a $(1/4
- \epsilon)$-approximation algorithm of Ohsaka [2023] (again for any
$\epsilon>0$). Finally, we show that Set Cover Reconfiguration is NP-hard to
approximate to within a factor of $2 - \epsilon$ for any constant $\epsilon >
0$, which matches the simple linear-time 2-approximation algorithm by Ito et
al. [TCS'11].
