Jump to content

Constraint logic problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Notadib (talk | contribs) at 21:23, 15 May 2019. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

Formal Definition of Constraint Logic Problems

Results

Applications