Constraint logic problem

In Computational Complexity Theory, constraint logic problems are a list of problems in constraint graph, a special graph with directed, weighted edges that satisfy special constraints (see below). These problems and their 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.