Solving SAT (and MaxSAT) with a quantum annealer: Foundations, encodings, and preliminary results.
Zhengbing BianFabián A. ChudakWilliam G. MacreadyAidan RoyRoberto SebastianiStefano VarottiPublished in: Inf. Comput. (2020)
Keyphrases
- boolean satisfiability
- boolean optimization
- sat solvers
- sat encodings
- sat solving
- sat instances
- sat problem
- maximum satisfiability
- branch and bound algorithm
- probabilistic planning
- weighted max sat
- randomly generated
- boolean formula
- max sat
- combinatorial problems
- orders of magnitude
- combinatorial optimization
- satisfiability problem
- symmetry breaking
- np complete problems
- artificial intelligence
- graph coloring
- solving hard
- pseudo boolean
- upper bound
- constraint satisfaction
- propositional satisfiability
- integer linear programming
- pseudo boolean constraints
- phase transition
- stochastic local search
- search space
- lower bound
- search algorithm
- np complete
- solving problems
- planning problems
- branch and bound
- quantum mechanics
- variable ordering
- exact solution
- search tree
- constraint satisfaction problems
- heuristic search