Hardness of Random Reordered Encodings of Parity for Resolution and CDCL.
Leroy ChewAlexis de ColnetFriedrich SlivovskyStefan SzeiderPublished in: AAAI (2024)
Keyphrases
- sat encodings
- clause learning
- sat solvers
- sat instances
- random instances
- unit propagation
- boolean satisfiability
- sat solving
- sat problem
- phase transition
- combinatorial problems
- orders of magnitude
- propositional satisfiability
- computational complexity
- max sat
- randomly generated
- constraint satisfaction problems
- planning problems
- constraint satisfaction
- satisfiability problem
- search tree
- np complete
- np hard
- search strategies
- combinatorial optimization
- information retrieval systems
- evolutionary algorithm
- search space
- lower bound
- information retrieval