Nondeterministic constraint logic
One can change this orientation by steps in which a single edge is reversed, subject to the same constraints.
These hardness results form the basis for proofs that various games and puzzles are PSPACE-hard or PSPACE-complete.
In the simplest version of nondeterministic constraint logic, each edge of an undirected graph has weight either one or two.
We call a configuration valid, if it satisfies the inflow constraint: each vertex must have an incoming weight of at least
We also define a move in a constraint graph to be the action of reversing the orientation of an edge, such that the resulting configuration is still valid.
[3] This problem asks if there exists an orientation of the edges that satisfies the inflow constraints given an undirected graph
It requires additional gadgets for simulating quantifiers and for converting signals carried on red edges into signals carried on blue edges (or vice versa), which can all be accomplished by combinations of and-vertices and or-vertices.
The proof of this involves the construction of crossover gadgets that allow two independent signals to cross each other.
Such a vertex is called a protected or, and it has the property that (in any valid orientation of the whole graph) it is not possible for both of the blue edges in the triangle to be directed inwards.
[2] Additionally, the constraint graphs can be required to have bounded bandwidth, and the problems on them will still remain PSPACE-complete.
In order to embed a QSAT formula, we need to create AND, OR, NOT, UNIVERSAL, EXISTENTIAL, and Converter (to change color) gadgets in the constraint graph.
[6] The original applications of nondeterministic constraint logic used it to prove the PSPACE-completeness of sliding block puzzles such as Rush Hour and Sokoban.
[2] Nondeterministic constraint logic has also been used to prove the hardness of reconfiguration versions of classical graph optimization problems including the independent set, vertex cover, and dominating set, on planar graphs of bounded bandwidth.
[2] This problem asks whether we can reach the victory condition of rush hour puzzle given an initial configuration.
