Solving Very Hard Problems: Cube-and-Conquer, a Hybrid SAT Solving Method
Solving Very Hard Problems: Cube-and-Conquer, a Hybrid SAT Solving Method
Marijn J.H. Heule, Oliver Kullmann, Victor W. Marek
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Best Sister Conferences. Pages 4864-4868.
https://doi.org/10.24963/ijcai.2017/683
A recent success of SAT solving has been the solution of the boolean Pythagorean Triples problem [Heule et al., 2016], delivering the largest proof yet, of 200 terabytes in size. We present this and the underlying paradigm Cube-and-Conquer, a powerful general method to solve big SAT problems, based on integrating the “old” and “new” methods of SAT solving.
Keywords:
Artificial Intelligence: search and constraint satisfaction