A Random Constraint Satisfaction Problem That Seems Hard for DPLL.
Harold S. ConnamacherPublished in: SAT (2004)
Keyphrases
- constraint satisfaction problems
- random instances
- random sat
- sat problem
- np complete
- constraint satisfaction
- phase transition
- sat instances
- randomly generated
- constraint programming
- constraint propagation
- constraint solving
- sat solvers
- satisfiability problem
- max sat
- search space
- davis putnam
- np hard
- graph coloring problems
- propositional satisfiability
- constraint networks
- combinatorial problems
- arc consistency
- non binary
- polynomial size
- binary csps
- decomposition methods
- propositional logic
- lower bound
- tractable subclasses
- pseudo boolean optimization
- reasoning problems
- constraint problems
- soft constraints
- boolean formula
- partial constraint satisfaction
- hard problems
- computational complexity