Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect
We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary operations, while satisfying the constraints at all times. Such problems appear natu...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2020
|
| Online Access: | https://hdl.handle.net/1721.1/128808 |
| _version_ | 1826203516541075456 |
|---|---|
| author | Demaine, Erik D |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary operations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration, sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE-completeness of the following decision problems: • Given two satisfying assignments of a planar monotone instance of NAE 3-SAT, can one assignment be transformed into the other by a sequence of variable flips such that the formula remains satisfied at every step? • Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum? • Given two points in {0,1}n contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P? These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the sets of instances that appear as input to the reconfiguration problems in our reductions lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length. |
| first_indexed | 2024-09-23T12:38:35Z |
| format | Article |
| id | mit-1721.1/128808 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:38:35Z |
| publishDate | 2020 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1288082022-09-28T09:10:48Z Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect Demaine, Erik D Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary operations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration, sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE-completeness of the following decision problems: • Given two satisfying assignments of a planar monotone instance of NAE 3-SAT, can one assignment be transformed into the other by a sequence of variable flips such that the formula remains satisfied at every step? • Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum? • Given two points in {0,1}n contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P? These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the sets of instances that appear as input to the reconfiguration problems in our reductions lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length. 2020-12-11T12:55:25Z 2020-12-11T12:55:25Z 2019-07 2019-02 2020-12-09T16:59:43Z Article http://purl.org/eprint/type/JournalArticle 0304-3975 https://hdl.handle.net/1721.1/128808 Jean Cardinal et al. “Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.” Theoretical Computer Science, 806 (July 2019): 332-343 © 2019 The Author(s) en 10.1016/J.TCS.2019.05.028 Theoretical Computer Science Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV arXiv |
| spellingShingle | Demaine, Erik D Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect |
| title | Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect |
| title_full | Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect |
| title_fullStr | Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect |
| title_full_unstemmed | Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect |
| title_short | Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect |
| title_sort | reconfiguration of satisfying assignments and subset sums easy to find hard to connect |
| url | https://hdl.handle.net/1721.1/128808 |
| work_keys_str_mv | AT demaineerikd reconfigurationofsatisfyingassignmentsandsubsetsumseasytofindhardtoconnect |