NP-Completeness of (k-SAT, r-UNk-SAT) and (LSAT>=k, r-UNLSAT>=k).
Tianyan DengDaoyun XuPublished in: FAW (2008)
Keyphrases
- sat solvers
- satisfiability problem
- sat problem
- sat solving
- stochastic local search algorithms
- phase transition
- propositional satisfiability
- sat instances
- pseudo boolean constraints
- stochastic local search
- search algorithm
- max sat
- boolean satisfiability
- search strategies
- orders of magnitude
- constraint satisfaction problems
- search procedures
- np complete
- state space
- variable ordering
- genetic algorithm
- data sets
- backtracking search
- database