Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMBINATORIAL RECONFIGURATION:
Reports tagged with combinatorial reconfiguration:
TR24-007 | 25th December 2023
Karthik C. S., Pasin Manurangsi

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

Revisions: 1

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 ... more >>>




ISSN 1433-8092 | Imprint