ResearchSAT solvingGSI-R-0013 · Note · Decision

Eleven SAT Competition 2025 main-track formulas listed as ‘unknown’ in the Global Benchmark Database have checkable refutation certificates.

Each of 11 formulas listed as ‘unknown’ in the Global Benchmark Database on 15 November 2026 is unsatisfiable, with a certificate checkable against its instance: for 4 Tseitin formulas, parity equations (sums of variables modulo 2) in the clauses sum to 0 = 1; for 7 round-robin formulas, clauses and sets of pairwise exclusive literals sum to 0 ≥ 1.

Before this work
The Global Benchmark Database (GBD) lists all 11 with result ‘unknown’ and track main_2025 [1], queried 15 November 2026; ‘unknown’ is the default value of the result feature [2]. The submitters of 10 of the 11 state that their formulas are unsatisfiable [3][4].
Evidence
One engine. A first program of ours refuted all 11; a second, written separately after the first program’s report, re-derived 7 of them with its own checker, which shares no code with the first program. The published certificates and checkers were written for this note. No one outside the lab has reviewed any of it.
What you can check
One half: the unsatisfiability of all 11 formulas is checkable per instance with one command below in under 20 seconds on a laptop. The ‘unknown’ listing can change (query hash=<hash> at benchmark-database.de); the timings cannot be reproduced from this page.
Not established
That any of the 11 was undecided or beyond existing solvers: ‘unknown’ is GBD’s default, submitters state 10 are unsatisfiable, other solvers decided 4, and we sought no earlier certificates.
Method
Not published.

What was known

A Tseitin formula has a variable per edge of a graph and, at each vertex, clauses fixing the sum of the incident variables modulo 2 to a given bit; it is unsatisfiable when the bits have an odd sum. Round-robin formulas encode a schedule in which every pair of n teams meets once and no team plays twice a day, within D < n − 1 days; multi-venue formulas add V one-match venues a day.

The submitters of the tseitin_grid and tseitin_d3 files state that Gaussian elimination refutes Tseitin formulas [3]. The submitters of the round-robin files state that all 20 of their instances are unsatisfiable because D < n − 1 and that the instances examine exactly-one cardinality reasoning [4].

Gauss–Jordan elimination on parity constraints in clause-learning solvers is published [5][6]. Cardinality constraints can be recovered from CNF [7]; with recovery a cutting-planes pseudo-Boolean solver decides all 14 binomial pigeonhole instances where CaDiCaL decides 3 [8].

The result

GBD hashGBD familyGBD fileVariablesClausesRefutationRe-derivedOther solvers
42f1311ce504db8cc0cb590a568da20atseitin-formulastseitin_n188_d3282752all 188 parity constraintsyesCryptoMiniSat 0.9 s
981c4e83c5dd3694af4c367958e0ee5ftseitin-formulastseitin_grid_n250_m250124,500496,008all 62,500 parity constraintsyesCryptoMiniSat 45.8 s
f3abc375afaf48c7eae21500b773bd21tseitin-formulastseitin_grid_n400_m400319,2001,273,608all 160,000 parity constraintsnonone: CryptoMiniSat, CP-SAT at limit
41d14756a06872844577fc0abddb58aatseitin-formulastseitin_d3_n100000150,000400,000all 100,000 parity constraintsyesCryptoMiniSat 71.5 s
6cb995b1c550beb579c53e27f6ca881aschedulingRoundRobin_n16_d131,56031,32014 clauses, 13 cliquesyesnone: HiGHS, Exact, CP-SAT at limit
6f6a20cd654701b5e7fe9e9e0e5e7787schedulingRoundRobin_n18_d152,29552,93816 clauses, 15 cliquesyesnone: HiGHS, Exact, CP-SAT at limit
78e8f5b0d59512cc4910fd63b4acb7faschedulingRoundRobin_n17_d141,90441,07215 clauses, 14 cliquesyesnone: HiGHS, Exact, CP-SAT at limit
cb66276897e4d1ff1368a4430598e11cschedulingRoundRobin_n17_d131,76837,26414 clauses, 13 cliquesyesHiGHS 77.7 s; Exact, CP-SAT at limit
35ec95b9b2398fb522db178855016ae0schedulingMVRoundRobin_n14_d10_v23,640127,49121 clauses, 20 cliquesnonone: CryptoMiniSat, CP-SAT at limit
3a1f1b4b9a521737cc760017fe9d8b43schedulingMVRoundRobin_n16_d10_v37,200372,72011 clauses, 10 cliquesnonone: CryptoMiniSat, CP-SAT at limit
c05d4d3ecd06a2e3942fea09159dd27bschedulingMVRoundRobin_n16_d10_v24,800212,52021 clauses, 20 cliquesnonone: CryptoMiniSat, CP-SAT at limit
Other solvers: CPU seconds, one thread, wall-clock limit 120 s, on the given clauses: CryptoMiniSat 5.17.0 with Gauss–Jordan elimination on, Exact 2.2.1 [9], HiGHS 1.15.1, CP-SAT 9.15, otherwise default options. Kissat and, on parity formulas, HiGHS timed out at 60 s wherever they ran.

A parity certificate is a set of parity constraints, each implied by the clauses that forbid its wrong-parity assignments, covering every variable an even number of times with right-hand sides summing to 1. A scheduling certificate is m clauses on disjoint variables whose literals the file’s binary clauses partition into m − 1 cliques of pairwise exclusive literals, so a model would make at least m of these literals true where at most m − 1 can be.

Timing, parity formulas

On 20 XOR-structured instances that our program refuted within 200 s, the better of Kissat’s and CaDiCaL’s wall time over our program’s wall time has geometric mean at least 341.6.

Timing, at-most-one formulas

On 19 instances that our program refuted within 60 s, the same ratio has geometric mean at least 44.5.

MeasureParity formulasAt-most-one formulas
Instances20 of the 2023–25 main tracks: 19 in GBD family tseitin-formulas, 1 in long-learned-clauses19 of the same tracks: 4 each of mutilated-chessboard, register-allocation, interval-matching and scheduling; 2 pigeon-hole; 1 fpga-routing
ComparatorsKissat 4.0.4 and CaDiCaL 3.0.1, default options, one thread, wall-clock limit 200 sthe same, wall-clock limit 60 s
Comparator runsboth timed out on 18 of 20; Kissat decided 2, CaDiCaL 1both timed out on 14 of 19; Kissat decided 4, CaDiCaL 2
Geometric mean of the ratio341.6, a lower bound: 18 of 20 comparator times are the limit44.5, a lower bound: 14 of 19 comparator times are the limit
Minimum of the ratio5.563.69
Runsone per instance, six at a timeone per instance, one at a time
Machine, load averageour shared 32-vCPU virtual machine, 24.2 to 27.9the same machine, 35.8 to 39.3
Ratio per instance: the better comparator wall time (the limit, if both timed out) over our program’s wall time. The times of our program are not released.

How to check it

h=42f1311ce504db8cc0cb590a568da20a
curl -sSL -o $h.cnf.xz https://benchmark-database.de/file/$h
curl -sSO https://generalised.si/files/sat-competition-refutations/parity_refute.py
python3 -I parity_refute.py find $h.cnf.xz cert.json
shasum -a 256 cert.json
Parity formulas: derive the certificate from the file and verify it. The SHA-256 of cert.json can be compared with the line for that hash in parity_certificates.sha256.
GBD hash 42f1311ce504db8cc0cb590a568da20a (matches file name)
certificate: 188 of 188 parity constraints
UNSATISFIABLE, verified: 188 parity constraints over 282 variables sum to 0 = 1
Output of find, under 0.1 s. The first line is the GBD hash computed from the file; it equals the file name for all 11.
curl -sSO https://generalised.si/files/sat-competition-refutations/parity_$h.json
python3 -I parity_refute.py check $h.cnf.xz parity_$h.json
For this hash the published 11 KB certificate equals cert.json; check verifies it alone.
h=6cb995b1c550beb579c53e27f6ca881a
curl -sSL -o $h.cnf.xz https://benchmark-database.de/file/$h
curl -sSO https://generalised.si/files/sat-competition-refutations/farkas_check.py
curl -sSO https://generalised.si/files/sat-competition-refutations/farkas_$h.json
python3 -I farkas_check.py $h.cnf.xz farkas_$h.json
Scheduling formulas: verify the published certificate of that hash.
GBD hash 6cb995b1c550beb579c53e27f6ca881a (matches file name)
UNSATISFIABLE, verified: 14 clause rows and 13 at-most-one rows sum to 0 >= 1
Output, under 0.1 s.
981c4e83…  UNSATISFIABLE, verified: 62500 parity constraints over 124500 variables sum to 0 = 1
f3abc375…  UNSATISFIABLE, verified: 160000 parity constraints over 319200 variables sum to 0 = 1
41d14756…  UNSATISFIABLE, verified: 100000 parity constraints over 150000 variables sum to 0 = 1
6f6a20cd…  UNSATISFIABLE, verified: 16 clause rows and 15 at-most-one rows sum to 0 >= 1
78e8f5b0…  UNSATISFIABLE, verified: 15 clause rows and 14 at-most-one rows sum to 0 >= 1
cb662768…  UNSATISFIABLE, verified: 14 clause rows and 13 at-most-one rows sum to 0 >= 1
35ec95b9…  UNSATISFIABLE, verified: 21 clause rows and 20 at-most-one rows sum to 0 >= 1
3a1f1b4b…  UNSATISFIABLE, verified: 11 clause rows and 10 at-most-one rows sum to 0 >= 1
c05d4d3e…  UNSATISFIABLE, verified: 21 clause rows and 20 at-most-one rows sum to 0 >= 1
Final line of the same commands for the other 9 instances (Apple M4, Python 3.15.0): the three large parity formulas take 2 to 6 s, up to 15 s when the machine is busy; the rest under 1 s.

Against brute force, no certificate of a satisfiable formula was accepted by the parity checker in 400 random systems on 9 variables, or by the at-most-one checker in 7,000 mutated or random certificates on formulas of at most 12 variables. A model of any of the 11 formulas, or a flaw in either program, would refute the result.

What it changes

Each scheduling certificate is one of the two counting arguments in [4]: D + 1 matches of one team against D days (5 formulas), or DV + 1 matches against DV day-and-venue slots (2 formulas).

Limits

  • Status. ‘unknown’ is GBD’s default [2]; the submitters of 10 of the 11 formulas state that they are unsatisfiable [3][4]; other solvers decided 4 of the 11 within 120 s. We found no description of tseitin_n188_d3 and did not search for earlier certificates; a dated one would close this.
  • Proof format. The certificates are parity and linear-programming objects checked by programs of ours; none is a clausal (DRAT, LRAT) or pseudo-Boolean (VeriPB) proof. Gauss–Jordan elimination can be proof-logged [10][11]; such a proof for each formula would close this.
  • Timings. One run per instance on loaded shared machines, against Kissat and CaDiCaL only, on instances our program refuted (the 19 are a family-stratified sample; the selection rule is not recorded). CryptoMiniSat with Gauss–Jordan elimination and a cutting-planes solver on both timing sets would close this.

Files

References

  1. [1]Global Benchmark Database, features hash, family, result and track, query hash=<hash>, read 15 November 2026. Link
  2. [2]A. Iser, C. Jabs, Global Benchmark Database, SAT 2024, doi:10.4230/LIPIcs.SAT.2024.18, arXiv:2405.10045v3 (14 January 2026), Example 1. Link
  3. [3]B. Bogaerts, J. Nordström, A. Oertel, Ç. U. Yıldırımoğlu, Crafted benchmark formulas requiring symmetry breaking and/or parity reasoning, Proceedings of SAT Competition 2023, University of Helsinki, B-2023-1, 67–69. Link
  4. [4]J. E. Reeves, A. Sheng, Round-robin tournament scheduling benchmarks, Proceedings of SAT Competition 2025, Vienna, 49. Link
  5. [5]M. Soos, K. Nohl, C. Castelluccia, Extending SAT solvers to cryptographic problems, SAT 2009, LNCS 5584, 244–257. Link
  6. [6]C.-S. Han, J.-H. R. Jiang, When Boolean satisfiability meets Gaussian elimination in a simplex way, CAV 2012, LNCS 7358. Link
  7. [7]A. Biere, D. Le Berre, E. Lonca, N. Manthey, Detecting cardinality constraints in CNF, SAT 2014, LNCS 8561, 285–301. Link
  8. [8]J. Elffers, J. Nordström, A cardinal improvement to pseudo-Boolean solving, AAAI 2020, 1495–1503, Figure 5. Link
  9. [9]J. Devriendt, Exact, a fork of the cutting-planes pseudo-Boolean solver RoundingSat (Python package), version 2.2.1, 10 July 2025. Link
  10. [10]M. Soos, R. E. Bryant, Proof generation for CDCL solvers using Gauss–Jordan elimination, arXiv:2304.04292 (April 2023). Link
  11. [11]S. Gocht, J. Nordström, Certifying parity reasoning efficiently using pseudo-Boolean proofs, AAAI 2021, 35(5), 3768–3777. Link

Cite asKishan Kumar, Refutation certificates for eleven SAT Competition formulas, GSI-R-0013, https://generalised.si/research/sat-competition-refutations, 2026.

Published16 November 2026

History
  • This account published.

All results