Constraint logic problem

In Computational Complexity Theory, 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, ie. 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.