On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

Venkatesan Guruswami, Karthik C. S., Pasin Manurangsi +2

Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some $\epsilon >0$ such that given as input a $k$-CSP inst…