Nondeterministic constraint logic

Last updated

In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. The constraint logic problem and its variants have been proven to be PSPACE-complete to determine whether there exists a sequence of moves that reverses a specified edge and are very useful to show various games and puzzles are PSPACE-hard or PSPACE-complete.

Contents

This is a form of reversible logic in that each sequence of edge orientation changes can be undone. The hardness of this problem has been used to prove that many games and puzzles have high game complexity.

Constraint graphs

An AND gate in constraint logic. As the minimum in-degree of the node is 2, the top edge can be out if and only if the two bottom edges are in. Constraint logic and gate.gif
An AND gate in constraint logic. As the minimum in-degree of the node is 2, the top edge can be out if and only if the two bottom edges are in.
Example of a constraint graph. Constraintgraph.png
Example of a constraint graph.

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. [2]

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. [2]

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. [2]

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. [2]

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

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 . In other words, the sum of the weights of the edges that enter a given vertex must be at least 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

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. [3] The reduction follows from QSAT and is outlined below.

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. [3]

Constraint Graph Satisfaction

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

Hard problems

The following problems, on and/or constraint graphs and their orientations, are PSPACE-complete: [2]

The proof that these problems are hard involves a reduction from quantified Boolean formulas, based on the logical interpretation of and/or constraint graphs. It requires additional gadgets for simulating quantifiers and for converting signals carried on red edges into signals carried on blue edges (or vice versa), which can all be accomplished by combinations of and-vertices and or-vertices. [2]

These problems remain PSPACE-complete even for and/or constraint graphs that form planar graphs. The proof of this involves the construction of crossover gadgets that allow two independent signals to cross each other. It is also possible to impose an additional restriction, while preserving the hardness of these problems: each vertex with three blue edges can be required to be part of a triangle with a red edge. Such a vertex is called a protected or, and it has the property that (in any valid orientation of the whole graph) it is not possible for both of the blue edges in the triangle to be directed inwards. This restriction makes it easier to simulate these vertices in hardness reductions for other problems. [2] Additionally, the constraint graphs can be required to have bounded bandwidth, and the problems on them will still remain PSPACE-complete. [4]

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:

The other gadgets can also be created in this manner. The full construction is available in Erik Demaine's website. [5] The full construction is also explained in an interactive way. [6]

Applications

The original applications of nondeterministic constraint logic used it to prove the PSPACE-completeness of sliding block puzzles such as Rush Hour and Sokoban. To do so, one needs only to show how to simulate edges and edge orientations, and vertices, and protected or vertices in these puzzles. [2]

Nondeterministic constraint logic has also been used to prove the hardness of reconfiguration versions of classical graph optimization problems including the independent set, vertex cover, and dominating set, on planar graphs of bounded bandwidth. In these problems, one must change one solution to the given problem into another, by moving one vertex at a time into or out of the solution set while maintaining the property that at all times the remaining vertices form a solution. [4]

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. [3]

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

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 . [3]

Dynamic Map Labeling

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

Related Research Articles

<span class="mw-page-title-main">Tree (graph theory)</span> Undirected, connected and acyclic graph

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

<span class="mw-page-title-main">Directed acyclic graph</span> Directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to information science to computation (scheduling).

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Eulerian path</span> Trail in a graph that visits each edge once

In graph theory, an Eulerian trail is a trail in a finite graph that visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any function ,

<span class="mw-page-title-main">Graph homomorphism</span> A structure-preserving correspondence between node-link graphs

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem. It does not matter whether many-one reducibility or Turing reducibility is used. Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.

<span class="mw-page-title-main">Minimum cut</span> Partition of a graph by removing fewest possible edges

In graph theory, a minimum cut or min-cut of a graph is a cut that is minimal in some metric.

<span class="mw-page-title-main">Rado graph</span> Infinite graph containing all countable graphs

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

<span class="mw-page-title-main">Instant Insanity</span>

Instant Insanity is the name given by Parker Brothers to their 1967 version of a puzzle which has existed since antiquity, and which has been marketed by many toy and puzzle makers under a variety of names, including: Devil's Dice (Pressman); DamBlocks (Schaper); Logi-Qubes (Schaeffer); Logi Cubes (ThinkinGames); Daffy Dots (Reiss); Those Blocks (Austin); PsykoNosis, and many others.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

<span class="mw-page-title-main">Directed graph</span> Graph with oriented edges

In mathematics, and more specifically in graph theory, a directed graph is a graph that is made up of a set of vertices connected by directed edges, often called arcs.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens.

In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

Games, Puzzles, and Computation is a book on game complexity, written by Robert Hearn and Erik Demaine, and published in 2009 by A K Peters. It is revised from Hearn's doctoral dissertation, which was supervised by Demaine. The Basic Library List Committee of the Mathematical Association of America has recommended it for inclusion in undergraduate mathematics libraries.

References

  1. ↑ "Constraint graphs". people.irisa.fr. Retrieved 2020-02-13.
  2. 1 2 3 4 5 6 7 8 Hearn, Robert A.; Demaine, Erik D. (2005), "PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation", Theoretical Computer Science , 343 (1–2): 72–96, arXiv: cs/0205005 , doi:10.1016/j.tcs.2005.05.008, MR   2168845, S2CID   656067 .
  3. 1 2 3 4 5 Demaine, Erik. "Non-Deterministic Constraint Logic" (PDF).
  4. 1 2 van der Zanden, Tom C. (2015), "Parameterized complexity of graph constraint logic", 10th International Symposium on Parameterized and Exact Computation, LIPIcs. Leibniz Int. Proc. Inform., vol. 43, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, pp. 282–293, arXiv: 1509.02683 , doi:10.4230/LIPIcs.IPEC.2015.282, ISBN   9783939897927, MR   3452428, S2CID   15959029 .
  5. ↑ Gurram, Neil. "Non Deterministic Constraint Logic" (PDF). Erik Demaine.
  6. ↑ "Constraint graphs (an interactive website that explains constraint graphs and the reduction from QBF). By François Schwarzentruber". people.irisa.fr. Retrieved 2020-02-20.
  7. ↑ Demaine, Erik D.; Hearn, Robert A. (2002-05-04). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv: cs/0205005 . Bibcode:2002cs........5005H.{{cite journal}}: Cite journal requires |journal= (help)
  8. ↑ Buchin, Kevin; Gerrits, Dirk H. P. (2013). "Dynamic Point Labeling is Strongly PSPACE-Complete". In Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah (eds.). Algorithms and Computation. Lecture Notes in Computer Science. Vol. 8283. Springer Berlin Heidelberg. pp. 262–272. doi:10.1007/978-3-642-45030-3_25. ISBN   9783642450303.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.