The SAT-UNSAT transition for random constraint satisfaction problems.
Nadia CreignouHervé DaudéPublished in: Discret. Math. (2009)
Keyphrases
- random constraint satisfaction problems
- sat solvers
- phase transition
- sat instances
- random instances
- constraint satisfaction
- sat problem
- random sat
- satisfiability problem
- propositional satisfiability
- max sat
- boolean satisfiability
- orders of magnitude
- search strategies
- randomly generated
- stochastic local search
- search space
- np complete
- np complete problems
- search tree
- constraint satisfaction problems
- combinatorial problems
- graph coloring
- boolean formula
- clause learning
- constraint programming
- hard problems
- data structure