Constraint satisfaction problems: complexity and algorithms.
Andrei A. BulatovPublished in: ACM SIGLOG News (2018)
Keyphrases
- constraint satisfaction problems
- constraint satisfaction
- combinatorial problems
- pseudo boolean optimization
- constraint programming
- computational problems
- space complexity
- computational complexity
- constraint optimization
- orders of magnitude
- problems in artificial intelligence
- decomposition methods
- constraint propagation
- non binary
- binary constraints
- tractable classes
- forward checking
- constraint solving
- worst case
- phase transition
- search space
- np hard
- arc consistency algorithm
- graph based representations
- objective function
- sat problem
- random instances
- decision problems
- np complete
- optimization problems