English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

We consider the computational complexity of reconfiguration problems, inwhich one is given two combinatorial configurations satisfying someconstraints, and is asked to transform one into the other using elementarytransformations, while satisfying the constraints at all times. Such problemsappear naturally in many contexts, such as model checking, motion planning,enumeration and sampling, and recreational mathematics. We provide hardnessresults for problems in this family, in which the constraints and operationsare particularly simple. More precisely, we prove the PSPACE-completeness ofthe following decision problems:  $\bullet$ Given two satisfying assignments to a planar monotone instance ofNot-All-Equal 3-SAT, can one assignment be transformed into the other by singlevariable `flips' (assignment changes), preserving satisfiability at every step?  $\bullet$ Given two subsets of a set S of integers with the same sum, can onesubset be transformed into the other by adding or removing at most threeelements of S at a time, such that the intermediate subsets also have the samesum?  $\bullet$ Given two points in $\{0,1\}^n$ contained in a polytope P specifiedby a constant number of linear inequalities, is there a path in the n-hypercubeconnecting the two points and contained in P?  These problems can be interpreted as reconfiguration analogues of standardproblems in NP. Interestingly, the instances of the NP problems that appear asinput to the reconfiguration problems in our reductions can be shown to lie inP. In particular, the elements of S and the coefficients of the inequalitiesdefining P can be restricted to have logarithmic bit-length.

Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect