GaloisSAT: Differentiable Boolean Satisfiability Solving via Finite Field Algebra
The Boolean satisfiability (SAT) problem, recognized as the first problem to be proven NP-complete, has emerged as a significant challenge in the field of computational complexity. It holds extensive applications across various domains, including optimization and verification. Despite the remarkable algorithmic advancements witnessed over the past two decades, the performance enhancements of SAT solvers have been relatively modest. The 2025 SAT Competition winner, for example, exhibits only approximately a 2X improvement over the 2006 winner’s performance after nearly 20 years of dedicated effort.
In light of these challenges, researchers have introduced GaloisSAT, a groundbreaking hybrid SAT solver that leverages both GPU and CPU architectures. This innovative approach combines a differentiable SAT solving engine, which utilizes modern machine learning infrastructure operating on GPUs, followed by a traditional Conflict-Driven Clause Learning (CDCL)-based SAT solving stage executed on CPUs.
Key Features of GaloisSAT
- Hybrid Architecture: GaloisSAT uniquely integrates GPU-accelerated machine learning with conventional SAT solving techniques.
- Differentiable SAT Solving: The use of differentiable programming allows for more effective learning methodologies, enhancing the solver’s performance.
- Benchmarking: GaloisSAT has been rigorously benchmarked against leading SAT solvers, specifically Kissat and CaDiCaL, within the SAT Competition 2024 benchmark suite.
Performance Metrics
The results from the benchmarking process indicate that GaloisSAT demonstrates significant improvements when measured against established state-of-the-art solvers. The performance is evaluated using the official SAT Competition metric PAR-2, which considers penalized average runtime with a timeout of 5,000 seconds and a penalty factor of 2. Notably, GaloisSAT achieves remarkable speedups in both satisfiable and unsatisfiable categories:
- Satisfiable Category: GaloisSAT achieves an impressive 8.41X speedup.
- Unsatisfiable Category: A respectable 1.29X speedup is observed.
Conclusion
The introduction of GaloisSAT marks a significant milestone in the ongoing quest to overcome the limitations of traditional SAT solvers. By merging modern machine learning techniques with established solving methodologies, GaloisSAT paves the way for future advancements in the field of computational complexity. The improvements in performance metrics suggest that this innovative approach could redefine the efficiency of SAT solving in various practical applications, from hardware verification to complex optimization problems.
Researchers and practitioners alike are encouraged to explore the capabilities of GaloisSAT, as it represents a promising step forward in the evolution of SAT solving technologies.