Exponential bounds for DPLL below the satisfiability threshold.
Dimitris AchlioptasPaul BeameMichael MolloyPublished in: SODA (2004)
Keyphrases
- propositional logic
- np complete
- sat problem
- random sat
- davis putnam logemann loveland
- sat solving
- satisfiability problem
- sat instances
- lower bound
- propositional satisfiability
- random constraint satisfaction problems
- upper bound
- sat solvers
- phase transition
- davis putnam
- clause learning
- upper and lower bounds
- error bounds
- computational complexity
- threshold selection
- industrial applications
- randomly generated
- first order logic
- average case
- belief revision
- lower and upper bounds
- boolean formula
- np hard
- confidence bounds
- model checking
- worst case bounds
- evolutionary algorithm
- adaptive threshold
- constraint satisfaction problems
- cnf formula
- computational properties
- worst case