TL;DR
This paper introduces "Cube-and-Conquer" (C&C), a novel hybrid SAT solving method that combines the strengths of "look-ahead" and "conflict-driven clause-learning" (CDCL) techniques. C&C excels at solving extremely difficult SAT problems, such as the boolean Pythagorean Triples problem, by intelligently partitioning large problems into smaller, manageable "cubes" for CDCL solvers to conquer, leading to significant performance gains.
What Problem Does This Paper Address?
The paper tackles the challenge of solving very hard concrete problem instances in NP, particularly those requiring proofs of unsatisfiability (NO-instances). While traditional approaches like specialized solvers (I), constraint satisfaction solvers (II), and SAT solvers (III) exist, SAT solvers (III) have become surprisingly powerful. However, even state-of-the-art CDCL SAT solvers, while excellent at finding short proofs, struggle when no such short proof exists. This limitation leaves a gap in efficiently solving problems where the search space is astronomically large and no obvious mathematical shortcuts are available. The authors aim to bridge this gap by integrating complementary solving paradigms.
Methods
The core innovation is the "Cube-and-Conquer" (C&C) method, a hybrid approach that leverages two distinct SAT solving strategies:
- Look-ahead: This "old" method excels at intelligently splitting a large problem into many smaller subproblems ("cubes"). It uses "in-processing" to estimate the outcomes of different search directions, aiming to create a balanced search tree. Its strength lies in its global overview and ability to partition problems effectively.
- Conflict-Driven Clause-Learning (CDCL): This "new" method is highly efficient at solving problems with local structure. It uses basic inferences and learns clauses from conflicts to prune the search space. CDCL solvers are responsible for the "SAT revolution" and are very effective on smaller, well-structured problems.
C&C works by first using a look-ahead solver to partition the problem into many subproblems (the "cubing phase"). These subproblems are then solved by CDCL solvers (the "conquer phase"). The key is to cut off the look-ahead search at an appropriate point, creating a large number of leaves (subproblems) that are then efficiently handled by CDCL. This approach is also described as "perfect parallelisation" due to its ability to distribute the conquered subproblems across many processors.
Datasets
The paper uses the boolean Pythagorean Triples problem as a primary example of a very hard problem instance. It also references problems from Ramsey theory as good benchmarks for SAT solving. No new datasets are introduced.
Key Insights and Ideas
- Complementary Strengths: Look-ahead solvers are good at "global" tree structures (splitting problems), while CDCL solvers are good at "local" DAG structures (solving subproblems). Neither method is optimal on its own for extremely hard problems.
- The "Astounding Observation": For many hard problems, the optimal performance is achieved by a hybrid approach with a specific number of subproblems (N), which is often significantly better than using either pure look-ahead or pure CDCL. This suggests a fundamental interaction between global and local problem structures.
- Proof Extraction is Crucial: For problems where no independent mathematical proof exists (like the Pythagorean Triples problem), extracting verifiable proofs of unsatisfiability is paramount. The 200TB proof for this problem highlights the scale and importance of this aspect.
- "Perfect Parallelisation": C&C enables highly efficient parallelization by creating a large number of independent subproblems that can be processed concurrently without significant load-balancing issues.
Key Results
The paper highlights the successful application of C&C to the boolean Pythagorean Triples problem, which required a 200TB proof of unsatisfiability. This problem was solved by first splitting it into 106 subproblems, and then further splitting these in parallel using 800 processors, resulting in a total of 40 * 10^6 subproblems. The total computation time was approximately 21,900 hours for cubing and 13,200 hours for conquering, totaling about 2 days with 800 cores. This demonstrates the power of C&C in tackling problems that would be intractable for individual methods.
Limitations and Future Work
- Problem Structure Understanding: The authors note that C&C needs a more solid theoretical foundation concerning problem structure and splitting heuristics. The "astounding observation" suggests that understanding this structure is key to optimizing the hybrid approach.
- Proof Mining: The paper suggests that "proof mining" could yield valuable insights into SAT solving and problem structure.
- Meaning of Large Proofs: The authors acknowledge ongoing discussions about the "meaning" of extremely large proofs (like the 200TB one) and their implications for mathematics.
- Foundations of Mathematics: The application of SAT to Ramsey theory, yielding a proof for a general existence statement beyond natural numbers, is highlighted as a potentially deeper aspect related to unsolved problems in the foundations of mathematics.
Summary updated