Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems.
Hubie ChenGeorg GottlobMatthias LanzingerReinhard PichlerPublished in: CoRR (2020)
Keyphrases
- constraint satisfaction problems
- constraint satisfaction
- constraint propagation
- np complete
- constraint programming
- np hard
- combinatorial problems
- non binary
- search space
- computational problems
- arc consistency
- sat problem
- partial constraint satisfaction
- fixed parameter tractable
- pseudo boolean optimization
- soft constraints
- temporal constraints
- finding optimal solutions
- phase transition
- solving constraint satisfaction problems
- lower bound
- objective function