In the simplest version of nondeterministic constraint logic, each edge of an undirected graph has weight either one or two. (The weights may also be represented graphically by drawing edges of weight one as red and edges of weight two as blue.) The graph is required to be a
cubic graph: each vertex is incident to three edges, and additionally each vertex should be incident to an even number of red edges. The edges are required to be oriented in such a way that at least two units of weight are oriented towards each vertex: there must be either at least one incoming blue edge, or at least two incoming red edges. An orientation can change by steps in which a single edge is reversed, respecting these constraints. More general forms of nondeterministic constraint logic allow a greater variety of edge weights, more edges per vertex, and different thresholds for how much incoming weight each vertex must have. A graph with a system of edge weights and vertex thresholds is called a
constraint graph. The restricted case where the edge weights are all one or two, the vertices require two units of incoming weight, and the vertices all have three incident edges with an even number of red edges, are called
and/or constraint graphs. The reason for the name
and/or constraint graphs is that the two possible types of vertex in an and/or constraint graph behave in some ways like an
AND gate and
OR gate in
Boolean logic. A vertex with two red edges and one blue edge behaves like an AND gate in that it requires both red edges to point inwards before the blue edge can be made to point outwards. A vertex with three blue edges behaves like an OR gate, with two of its edges designated as inputs and the third as an output, in that it requires at least one input edge to point inwards before the output edge can be made to point outwards. Typically, 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 the Constraint logic problem ==