**Reference**:- Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno, “On the Complexity of Reconfiguration Problems”,
*Theoretical Computer Science*, volume 412, number 12–14, 2011, pages 1054–1065. **Abstract**:- Reconfiguration problems arise when we wish to find a step-by-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
**Comments**:- This paper is also available from ScienceDirect.
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PDF (451k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- NPReconfiguration_ISAAC2008 (On the Complexity of Reconfiguration Problems)
- SubsetSumReconfiguration_JOCO (Approximability of the Subset Sum Reconfiguration Problem)
- NPReconfiguration_WADS2009 (Reconfiguration of List Edge-Colorings in a Graph)

See also other papers by Erik Demaine.

Last updated February 26, 2024 by Erik Demaine.