A Survey of Lower Bounds for Satisfiability and Related Problems.
Dieter van MelkebeekPublished in: Electron. Colloquium Comput. Complex. (2007)
Keyphrases
- related problems
- lower bound
- upper bound
- satisfiability problem
- branch and bound
- np hard
- branch and bound algorithm
- np complete
- computational complexity
- lower and upper bounds
- phase transition
- objective function
- terminological reasoning
- broadly applicable
- stable marriage
- decision procedures
- upper and lower bounds
- propositional logic
- optimal solution
- sat problem
- range searching
- worst case
- sample complexity
- linear programming
- quadratic assignment problem
- max sat
- optimal cost
- vc dimension
- search algorithm