On the complexity of reconfiguration problems

On the complexity of reconfiguration problems

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

Full description

Bibliographic Details
Main Authors: Ito, Takehiro, Demaine, Erik D., Harvey, Nicholas J.A., Papadimitriou, Christos H., Sideri, Martha, Uehara, Ryuhei, Uno, Yushi
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Elsevier 2015
Online Access:http://hdl.handle.net/1721.1/99966
https://orcid.org/0000-0003-3803-5703

Internet

http://hdl.handle.net/1721.1/99966
https://orcid.org/0000-0003-3803-5703

Similar Items