Fine-Grained Time Complexity of Constraint Satisfaction Problems.
Peter JonssonVictor LagerkvistBiman RoyPublished in: ACM Trans. Comput. Theory (2021)
Keyphrases
- fine grained
- constraint satisfaction problems
- constraint satisfaction
- coarse grained
- constraint programming
- np complete
- constraint propagation
- search space
- combinatorial problems
- arc consistency
- non binary
- constraint solving
- access control
- solving constraint satisfaction problems
- constraint networks
- soft constraints
- computational complexity
- np hard
- decision problems
- decomposition methods
- constraint problems
- space complexity
- data lineage
- forward checking
- partial constraint satisfaction
- partial assignment
- pseudo boolean optimization
- backtracking search
- global constraints
- sat solvers
- worst case