A Hierarchy of Tractable Subclasses for SAT and Counting SAT Problems.
Stefan AndreiGheorghe GrigorasMartin C. RinardRoland H. C. YapPublished in: SYNASC (2009)
Keyphrases
- sat problem
- tractable subclasses
- constraint satisfaction problems
- constraint satisfaction
- boolean satisfiability
- np complete
- constraint propagation
- max sat
- sat instances
- constraint programming
- sat solving
- propositional satisfiability
- backtracking search
- np hard
- combinatorial problems
- search space
- sat solvers
- davis putnam
- satisfiability problem
- solving hard
- constraint networks
- arc consistency
- np complete problems
- maximum satisfiability
- search algorithm
- randomly generated
- symmetry breaking
- clause learning
- phase transition
- branch and bound
- decision problems