Benchmark status · measured October 2026
SAT Competition 2024 instances answered correctly that Kissat 4.0.4 cannot resolve in 10 s.
pcmax scheduling ×2 · 90 ms, 217 ms
clique-colouring ×6 · 176–444 ms
Correct at SATLIB sizes (n=50, n=100) — no wrong answers, none unresolved. Outside that verified size range the engine defers to complete search rather than committing: at n=150–200, 15 of 16 unsatisfiable instances resolved correctly, one returned no answer.
Every tested instance whose unsatisfiability follows from its construction, returned without search.
Geometric mean across 16 random 3-SAT instances at n=75–100, every verdict in agreement.
On all 145 labelled SC2024 instances: 50 commitments, 39 correct —
78% precision. Forty-eight of those commitments were made without complete
search and are labelled heuristic; the other two were decided by
complete search or by a satisfying assignment checked against every clause, and
are labelled proved.
The no-search path returns UNSAT on some dense satisfiable instances. Of 50 SC2024 commitments, 11 are wrong. Ten are satisfiable instances reported as UNSAT — six of those from generators that plant a solution by construction. One is the reverse: an unsatisfiable instance reported as SAT. Kissat 4.0.4 resolved 4 instances the engine left unresolved.
Verdicts from that path are labelled heuristic;
everything decided by complete search or backed by a checked
assignment is labelled proved.
Set — 145 SC2024 labelled instances; ground truth from the published competition results (
backend/sc2024_ground_truth.json). Head-to-head timings
against Kissat 4.0.4, minimum of five runs per instance.
Figures stated at the scope they were measured.Reproduce — regression suite, per-instance results and the head-to-head harness are in the project repository.
| Time | n | Result | Tier | Method | ms | Decisions |
|---|---|---|---|---|---|---|
| no classifications yet | ||||||