Hardness of Random Reordered Encodings of Parity for Resolution and CDCL.
Leroy ChewAlexis de ColnetFriedrich SlivovskyStefan SzeiderPublished in: CoRR (2024)
Keyphrases
- sat encodings
- sat solvers
- clause learning
- sat instances
- random instances
- unit propagation
- boolean satisfiability
- sat solving
- phase transition
- graph coloring
- orders of magnitude
- combinatorial problems
- satisfiability problem
- search tree
- constraint satisfaction problems
- max sat
- lower bound
- search space
- propositional satisfiability
- sat problem
- conjunctive normal form
- constraint satisfaction
- computational complexity
- integer linear programming
- randomly generated