Nondeterministic constraint logic

<p>

In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, nondeterministic constraint logic is a combinatorial system in which an <a href="/facts/Orientation_(graph_theory)/GV2KdNtn">orientation</a> is given to the edges of a weighted <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a>, subject to certain constraints. One can change this orientation by steps in which a single edge is reversed, subject to the same constraints. This is a form of <a href="/facts/Reversible_computing/yEum13Vs">reversible logic</a> in that each sequence of edge orientation changes can be undone.
</p><p><a href="/facts/Reconfiguration/nW4XxGAR">Reconfiguration</a> problems for constraint logic, asking for a sequence of moves to connect certain states, connect all states, or reverse a specified edge have been proven to be <a href="/facts/PSPACE-complete/gkV3vHfX">PSPACE-complete</a>. These hardness results form the basis for proofs that various games and puzzles are PSPACE-hard or PSPACE-complete.
</p>

Nondeterministic constraint logic open-in-new

Nondeterministic constraint logic