| On the Complexity of Reconfiguration Problems (2009) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. Reconfiguration problems arise when we wish to find a stepby-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||