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.

Formal Definition of Constraint Logic Problems

The following problems belong to family of constraint logic problems:

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.^[1]

Edge Reversal

This problem 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.^[1]

Non-Deterministic Constraint Logic

Given a constraint graph, a starting configuration and an ending configuration, does there exist 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.^[1]

Results

Applications

^ ^a ^b ^c Demaine, Eric. "Non-Deterministic Constraint Logic" (PDF). {{cite web}}: Cite has empty unknown parameter: |dead-url= (help)

[:0-1] Demaine, Eric. "Non-Deterministic Constraint Logic" (PDF). {{cite web}}: Cite has empty unknown parameter: |dead-url= (help)

[1]