Nondeterministic constraint logic とは

理論的計算機科学では、非決定論的制約論理は、一定の制約を受けて、重み付けされた無向グラフのエッジに方位が与えられる組合せシステムである。 1つのエッジが反転され、同じ制約に従うステップによって、この向きを変更することができる。指定されたエッジを反転させる一連の動きが存在するかどうかを判断するのはPSPACE-completeです。
これは、エッジ方向の変化の各シーケンスを元に戻すことができるという可逆ロジックの一形態です。この問題の硬度は、多くのゲームやパズルがゲームの複雑さが高いことを証明するために使用されています。