On Approximability of Satisfiable k-CSPs: IV.
Amey BhangaleSubhash KhotDor MinzerPublished in: CoRR (2023)
Keyphrases
- sat problem
- constraint satisfaction problems
- constraint satisfaction
- satisfiability problem
- phase transition
- np complete
- randomly generated
- approximation algorithms
- arc consistency
- solving constraint satisfaction problems
- random instances
- constraint problems
- constraint propagation
- non binary
- search space
- max sat
- symmetry breaking
- propositional satisfiability
- tree decomposition
- constraint programming
- partial constraint satisfaction
- decision problems
- polynomial time approximation
- backtracking algorithm
- distributed constraint satisfaction
- computational complexity
- worst case
- np hard
- forward checking