CSPs and Connectedness: P/NP Dichotomy for Idempotent, Right Quasigroups.
Robert W. McGrailJames M. BelkSolomon GarberJapheth WoodBenjamin FishPublished in: SYNASC (2014)
Keyphrases
- arc consistency
- constraint satisfaction problems
- constraint satisfaction
- constraint propagation
- constraint programming
- space complexity
- non binary
- solving constraint satisfaction problems
- soft constraints
- constraint networks
- global constraints
- morphological operators
- hypertree decomposition
- path consistency
- geometrical interpretation
- connected components
- decision diagrams
- branch and bound search
- symmetry breaking
- search space
- backtracking algorithm
- partial constraint satisfaction
- forward checking
- constraint problems
- tree decomposition
- pac learning
- image analysis
- optimal solution