One-step replica symmetry breaking of random regular NAE-SAT.
Danny NamAllan SlyYoungtak SohnPublished in: FOCS (2021)
Keyphrases
- symmetry breaking
- boolean satisfiability
- sat solvers
- constraint programming
- sat solving
- propositional satisfiability
- graph coloring
- search tree
- pseudo boolean
- randomly generated
- global constraints
- constraint satisfaction problems
- boolean optimization
- sat problem
- integer linear programming
- search strategies
- constraint satisfaction
- search algorithm
- phase transition
- database systems
- combinatorial problems
- sat instances
- special case
- search space