# Introduction to Reconfiguration
## 3 Tools for Proving the Complexity of Reachability  
By considering reconfiguration as a framework that highlights the commonality of a large variety of source problems, often studied in isolation, it becomes possible to devise general approaches and detect patterns. In the initial results obtained on reachability, the dividing line between tractable and intractable problems followed the dividing line for the source problems. Typically an intractable source problem is NP-complete and an intractable reachability problem is PSPACE-complete, where the class PSPACE includes all problems that can be solved using polynomial space [12]. Polynomial-time reachability algorithms have been developed for tractable source problems such as 2-Coloring[31; 32; 33], Matching[4], Minimum Spanning Tree[4], and 2-Satisfiability[34]. Reachability has been shown to be PSPACE-complete for many NP-complete source problems, such as Clique[4], 4-Coloring[35], Independent Set[4; 17], 3-Satisfiability[34], Vertex Cover[4], Dominating Set[4], List Edge-Coloring[36], List \(L(2,1)\)-Labeling[37], Integer Programming[4], Steiner Tree[38], and Set Cover[4]. As was conjectured early on [4], there are exceptions to the general pattern. One such exception is 3-Coloring[33], for which the source problem is NP-hard but the reachability problem is solvable in polynomial time. The problem Shortest Path is an example that breaks the pattern in the opposite direction, as the source problem is solvable in polynomial time but the reachability problem is PSPACE-complete [39]. What remains unclear is which properties of source problems result in their deviating from the general pattern of NP-hard source problems resulting in PSPACE-hard reachability problems; further work is needed on this question. Many of the reductions used in proving PSPACE-hardness results mimic NP-hardness reductions on the source problems. The basis for these hardness results is the reconfiguration of the _Nondeterministic Constraint Logic (NCL) machine_, an undirected graph with integer weights on vertices and edges [16]. Reconfiguration on the NCL machine uses as solutions orientations of the edges such that the weight of each vertex is no greater than the sum of the weights of incoming edges; a reconfiguration step is the changing of the direction of a single edge. By forming substructures that behave like OR and AND gates (Figure 3), the problem was shown to be PSPACE-complete by a reduction from Quantified Boolean Formula[12]. The result on NCL Reconfiguration was then used as the basis for proving the PSPACE-completeness of sliding tokens on a graph [16], which in turn became the basis for many of the known PSPACE-completeness results for reconfiguration. In subsequent work, NCL has been generalized to include neutral, undirected edges; a new type of gadget has been used to complete the classification of reachability for List Edge-Coloring Reconfiguration to be solvable in polynomial time for at most three colors and PSPACE-complete otherwise [40]. As yet, there are few general algorithmic paradigms for reachability. Many algorithms in fact solve the connectivity problem as well, as they consist of identifying a _canonical configuration_ for a particular instance and then showing that there is a reconfiguration sequence between any input solution and the canonical configuration (and hence a sequence from the source solution to the target solution that goes through the canonical configuration). When reachability is intractable, possible approaches include an analysis using parameterized complexity (as discussed in detail in Section 5) and determining the dividing line between classes of instances for which the problem is tractable and those for which it is not (as discussed in Section 4 for the source problem Independent Set). For a specific problem, a natural starting point is to determine whether the dividing line for reachability is the same as the dividing line for the source problem.