Editing PSPACE-complete (section)

===Reconfiguration===
[[Reconfiguration]] problems concern the connectivity of a [[state space]] of solutions to a combinatorial problem. For instance, testing whether two 4-colorings of a graph can be connected to each other by moves that change the color of one vertex at a time, maintaining at each step a valid 4-coloring, is PSPACE-complete,{{r|boncer}} even though the same problem for 3-colorings can be solved in polynomial time.{{r|jkkpp}} Another family of reconfiguration problems, used similarly to quantified Boolean formulas as the basis for PSPACE-completeness proofs of many other problems in this area, involve [[nondeterministic constraint logic]], in which the states are [[Orientation (graph theory)|orientations]] of a constraint graph subject to certain constraints on how many edges must be oriented inwards at each vertex, and in which the moves from state to state reverse the orientation of a single edge.{{r|hearn-demaine}}