On the complexity of reconfiguration problems
On the complexity of reconfiguration problems
复制标题
DOI：
10.1016/j.tcs.2010.12.005
复制
发表时间：
2011-03-18
影响因子：
1.1
通讯作者：
Uno, Yushi
中科院分区：
文献类型：
--
作者：
Ito, Takehiro;Demaine, Erik D.;Uno, Yushi
当我们希望在一个问题的两个可行解之间找到一个逐步的转换，使得所有的中间结果也是可行的时，就会出现重构问题。我们证明了一个主机的重新配置问题来自NP完全问题是PSPACE完全的，而有些也是NP难近似。相比之下，P中问题的几个重构版本可以在多项式时间内解决。(C)2010 Elsevier B.V.保留所有权利。
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. (C) 2010 Elsevier B.V. All rights reserved.