Research map / Learning theory and algorithms / Combinatorial and search optimization
A SAT + Computer Algebra System Verification of the Ramsey Problem R(3, 8) (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Produces the first certifiable (DRAT-checkable) proof that the Ramsey number R(3,8)=28 by combining a CDCL SAT solver (MapleSAT) with a computer algebra system that generates orderly-generation symmetry-breaking blocking clauses.
Problem
Determining the Ramsey number R(3,8), which was previously computed by McKay and Min (1992) without a verifiable proof; SAT-only encodings struggle with symmetry in Ramsey search spaces.
Approach
Use a CAS to generate canonical-form (orderly generation) blocking clauses dynamically during SAT solving, with each clause's noncanonicity witnessed by a permutation recorded in the DRAT proof, so the whole UNSAT result is independently checkable.
Key results
- R(3,8)=28 was verified: 28-vertex (3,8)-graph is UNSAT using MapleSAT+CAS after 96 hours on an AMD EPYC 7763 with 16 GiB RAM.
- A 30 GiB DRAT proof was generated and verified in 63 hours.
- SAT+CAS was reported to be orders of magnitude faster than SAT-only; for R(3,7) on 23 vertices SAT+CAS solved in 2 minutes while SAT-only did not finish in 24 hours.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add CAS-generated symmetry-breaking blocking clauses (ablation) | SAT solver · R(3,7), 23 vertices | solve time: 2 minutes vs. could not solve it in 24 hours | Helped |
| add CAS-guided symmetry breaking (ablation) | SAT solver · R(3,8), 28 vertices | solve time | Helped |
Limitations
- Verification requires a 30 GiB DRAT proof and 63 hours of checking.
- Full solve took 96 hours on a single 16 GiB machine.
- Relies on trusting the CAS-derived trusted clauses, which need a modified DRAT checker.
Experimental setup
Benchmarks: R(3,8) on 28 vertices (UNSAT) R(3,8) on 27 vertices (SAT) R(3,7) on 23 vertices (ablation)
Metrics: solve time proof size verification time
Baselines: SAT-only solver encoding McKay and Min (1992) computation
Builds on: SAT+CAS paradigm orderly generation DRAT-trim MapleSAT
Closest papers by meaning
- A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem (Student Abstract) (AAAI 2024 · similarity 0.85)
- Breaking Symmetries in Quantified Graph Search: A Comparative Study (AAAI 2025 · similarity 0.84)
- SAT-Based Techniques for Lexicographically Smallest Finite Models (AAAI 2024 · similarity 0.83)
- Computationally Hard Problems Are Hard for QBF Proof Systems Too (AAAI 2025 · similarity 0.83)
- Parameterization of (Partial) Maximum Satisfiability above Matching in a Variable-Clause Graph (AAAI 2024 · similarity 0.83)
- End-to-End Verification for Subgraph Solving (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.