Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems).
Manuel BodirskyAntoine MottetMiroslav OlsákJakub OprsalMichael PinskerRoss WillardPublished in: CoRR (2019)
Keyphrases
- constraint satisfaction problems
- constraint satisfaction
- constraint propagation
- constraint programming
- np complete
- non binary
- arc consistency
- search space
- combinatorial problems
- np hard
- domain independent
- finite domain
- domain specific
- backtracking search
- global constraints
- constraint optimization
- forward checking
- soft constraints
- arithmetic constraints
- solving constraint satisfaction problems
- tractable classes
- finding optimal solutions
- sat problem
- pseudo boolean optimization
- constraint solver
- path consistency
- constraint networks
- constraint graph
- reasoning problems
- constraint solving
- computational complexity
- disjunctive temporal
- lower bound