Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas.

Dimitris Achlioptas Ricardo Menchaca-Mendez

Published in: SAT (2012)

Keyphrases

lower bound
max sat
sat problem
cnf formula
stochastic local search
upper bound
np complete
orders of magnitude
satisfiability problem
randomly generated
random instances
sat instances
data structure
sat solvers
optimization problems
state space
expert systems
propositional satisfiability
objective function