Introduction
In the field of automated reasoning, researchers often face a trade-off between search efficiency and mathematical expressiveness. SAT and SMT solvers are world-class at navigating massive, complex logic spaces to find solutions or proofs, yet they struggle to "understand" high-level mathematical concepts. For instance, encoding a property like "is this graph Hamiltonian?" into raw Boolean logic is notoriously difficult and computationally inefficient.
Conversely, Computer Algebra Systems (CAS) like Maple or Sage possess deep knowledge of mathematical structures and can perform complex symbolic computations with ease. However, they lack the robust search capabilities required to find counterexamples to open conjectures in large state spaces. MATHCHECK is a hybrid "SAT+CAS" system designed to bridge this gap by embedding the domain-specific power of a CAS directly into the search loop of a SAT solver.
The MATHCHECK Architecture
The MATHCHECK system functions similarly to a "DPLL(T)" SMT solver, but where the "Theory" (T) is an entire CAS. This allows mathematicians to use the CAS to define complex predicates while the SAT solver handles the heavy lifting of the search.
As illustrated in the architecture diagram, the process follows a specific workflow:
- Input: A mathematical conjecture is expressed as a combination of SAT predicates (simple logic) and CAS predicates (code written in Python/Sage).
- The Inner Loop: As the SAT solver (Glucose) searches for a counterexample, it periodically queries the CAS (SAGE) with partial assignments.
- Learning: If the CAS determines that a partial assignment violates a mathematical property, it generates "learned clauses"—mathematical lemmas—that are fed back into the SAT solver to prune large sections of the search tree.
Case Study: Hypercube Conjectures
The authors evaluated MATHCHECK on a specific challenge in graph theory: verifying Conjecture 1 (Ruskey and Savage). This conjecture posits that any matching in a $d$-dimensional hypercube ($Q_d$) can be extended to a Hamiltonian cycle.
Testing the system on dimensions $d=3, 4,$ and $5$ demonstrated the power of the hybrid approach. While a pure SAT encoding of Hamiltonian cycles would require a massive, complex set of constraints, writing a predicate to check for a Hamiltonian cycle in SAGE takes only a few lines of Python code.
Key Results and Insights
MATHCHECK successfully verified the Ruskey and Savage conjecture for the 5-dimensional hypercube ($Q_5$), a feat previously out of reach for standard solvers. Previous known results had only reached $d=4$.
Key performance factors included:
- Efficiency: For $Q_5$, the system completed the verification in just under 8 hours on a standard laptop, performing approximately 348,150 CAS predicate checks. For lower dimensions ($d \leq 4$), the system finished in under 20 seconds.
- Search Space Reduction: The authors utilized mathematical insights, such as focusing only on "maximal forbidden matchings," to reduce the number of cases the SAT solver had to check.
- Symmetry Breaking: By exploiting the inherent symmetry of hypercubes, the system could fix certain variables (e.g., ensuring a specific vertex remains unmatched) to further speed up the search without losing generality.
Limitations and Future Work
Despite the success with $Q_5$, the authors note that $Q_6$ and higher dimensions remain likely out of reach without discovering further mathematical lemmas to prune the search space more aggressively.
Future development for MATHCHECK involves integrating it with proof-producing solvers (like VeriT) to generate independently verifiable "certificates" of results. Additionally, the authors intend to extend the system to other domains, such as number theory and topology, where CAS systems already possess robust built-in libraries.
Summary updated