A sharp threshold in proof complexity yields lower bounds for satisfiability search.
Dimitris AchlioptasPaul BeameMichael S. O. MolloyPublished in: J. Comput. Syst. Sci. (2004)
Keyphrases
- lower bound
- search algorithm
- computational complexity
- worst case
- search space
- upper bound
- search strategy
- search strategies
- objective function
- satisfiability problem
- branch and bound algorithm
- branch and bound
- symmetry breaking
- search methods
- decision problems
- search tree
- decision procedures
- stochastic local search
- optimal solution