A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors.
Stephan KottlerMichael KaufmannCarsten SinzPublished in: SAT (2008)
Keyphrases
- satisfiability problem
- np complete
- np hard
- lower bound
- worst case
- sat instances
- sat solvers
- sat problem
- randomly generated
- upper bound
- branch and bound algorithm
- stochastic local search algorithms
- constraint satisfaction problems
- phase transition
- special case
- stochastic local search
- approximation algorithms
- optimal solution
- closely related
- linear programming
- scheduling problem
- max sat
- np hardness
- minimum cost
- computational complexity
- greedy heuristic
- error bounds
- knapsack problem
- objective function
- propositional satisfiability
- remains np hard
- hidden structure
- conjunctive normal form
- set cover
- integer programming
- constraint satisfaction
- decision problems
- search algorithm
- search space
- vc dimension
- boolean satisfiability
- sat encodings
- sat solving
- randomly generated problem instances
- branch and bound