Constraint logic problem

In computational complexity theory, the constraint logic problem is a problem in constraint graph, a special graph with weighted edges that satisfy special constraints (see below). This problem and its variants have been proven to be PSPACE-Complete and are very useful to show various games and puzzles are PSPACE-hard or PSPACE-complete.

Constraint Graphs

Constraint logic problems are defined around finding valid configurations of constraint graphs. Constraint graphs are undirected graphs with two types of edges:

• red edges with weight $1$
• blue edges with weight $2$

We use constraint graphs as computation models, where we think of the entire graph as a machine. A configuration of the machine consists of the graph along with a specific orientation of its edges. We call a configuration valid, if it satisfies the inflow constraint: each vertex must have an incoming weight of at least $2$. In other words, the sum of the weights of the edges that enter a given vertex must be at least $2$ more than the sum of the weights of the edges that exit the vertex.

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.

Formal Definition

Non-Deterministic Constraint Logic

Suppose we are given a constraint graph, a starting configuration and an ending configuration. This problem asks if there exists a sequence of valid moves that move it from the starting configuration to the ending configuration This problem is PSPACE-Complete for 3-regular or max-degree 3 graphs. The reduction follows from QSAT and is outlined below.

This problem has multiple variants:

Planar Non-Deterministic Constraint Logic

The above problem is PSPACE-Complete even if the constraint graph is planar, i.e. no the graph can be drawn in a way such that no two edges cross each other. This reduction follows from Planar QSAT.

Edge Reversal

This problem is a special case of the previous one. It asks, given a constraint graph, if it is possible to reverse a specified edge by a sequence of valid moves. Note that this could be done by a sequence of valid moves so long as the last valid move reverses the desired edge. This problem has also been proven to be PSPACE-Complete for 3-regular or max-degree 3 graphs.

Constraint Graph Satisfaction

This problem asks if there exists an orientation of the edges that satisfies the inflow constraints given an undirected graph $G$. This problem has been proven to be NP-Complete.

Proof of PSPACE-hardness

The reduction follows from QSAT. 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. The idea goes as follows:

• An AND vertex is a vertex such that it has two incident red edges (inputs) and one blue incident edge (output).
• An OR vertex is a vertex such that it has three incident blue edges (two inputs, one output).

The other gadgets can also be created in this manner. The full construction is available in Eric Demaine's website.

Applications

Constraint logic problems provide us with a fruitful foundation to prove PSPACE-hardness results for several well-known puzzles.

Reconfiguration 3SAT

Given a 3-CNF formula and two satisfying assignments, this problem asks whether it is possible find a sequence of steps that take us from one assignment to the others, where in each step we are allowed to flip the value of a variable. This problem can be shown PSPACE-complete via a reduction from the Non-deterministic Constraint Logic problem.

Sliding-Block Puzzles

This problem asks whether we can reach a desired configuration in a sliding block puzzle given an initial configuration of the blocks. This problem is PSPACE-complete, even if the rectangles are dominoes.

Rush Hour

This problem asks whether we can reach the victory condition of rush hour puzzle given an initial configuration. This problem is PSPACE-complete, even if the blocks have size $1\times 2$.

Dynamic Map Labeling

Given a static map, this problem asks whether there is a smooth dynamic labeling. This problem is also PSPACE-complete.