A Survey of Lower Bounds for Satisfiability and Related Problems.
Dieter van MelkebeekPublished in: Found. Trends Theor. Comput. Sci. (2006)
Keyphrases
- related problems
- lower bound
- upper bound
- satisfiability problem
- branch and bound algorithm
- branch and bound
- objective function
- np hard
- np complete
- quadratic assignment problem
- worst case
- propositional logic
- upper and lower bounds
- satisfiability testing
- broadly applicable
- range searching
- max sat
- stable marriage
- computational complexity
- quantified boolean formulas
- decision procedures
- lower and upper bounds
- sat problem
- phase transition
- vc dimension
- cnf formula
- linear programming relaxation
- sat instances
- online algorithms
- boolean formula
- sample complexity
- uniform distribution
- scheduling problem
- optimal solution