  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 there is some $\varepsilon>0$ such
that 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-\varepsilon)$ 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, thus establishing 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.
  We also prove that the aforementioned $k$-CSP Reconfiguration problem is
NP-hard to approximate to within a factor of $1/2 + \varepsilon$ (for any
$\varepsilon>0$) when $k=2$. We complement this with a $(1/2 -
\varepsilon)$-approximation polynomial time algorithm, which improves upon a
$(1/4 - \varepsilon)$-approximation algorithm of Ohsaka [2023] (again for any
$\varepsilon>0$).
  Finally, we show that Set Cover Reconfiguration is NP-hard to approximate to
within a factor of $2 - \varepsilon$ for any constant $\varepsilon > 0$, which
matches the simple linear-time 2-approximation algorithm by Ito et al.
[TCS'11].
