Research · Papers · Exact answers in open problems · ML-098
Failure of SMS standalone LRAT certificate verification for Kochen-Specker n = 18
Standalone lrat-check of smsg -v 18 --lrat-output fails due to unintegrated --sym-break-clauses outside the LRAT chain.
Published 2026-09-06
For everyone
Plain summary
When automated solvers prove a math problem has no solution, they output a step-by-step certificate that an independent program can check. The Symmetry-Modulo-Solver (SMS) ran on the Kochen-Specker n = 18 problem, reported no solution in 35 seconds, and wrote a 530 MB proof file. Standard proof checkers failed immediately because SMS wrote its symmetry rules to a separate data file instead of embedding them into the main proof chain. Because the checker cannot read those external rules, it rejects the certificate at line zero. Standalone SMS proof files from this build cannot be validated.
Result
Standalone verification of the LRAT certificate produced by smsg -v 18 --lrat-output for Kochen-Specker n = 18 fails under lrat-check. The checker exits with "verification incomplete, last line checked = 0 / NOT VERIFIED" because symmetry-breaking clauses emitted via --sym-break-clauses are omitted from the LRAT derivation chain.
Setting and definitions
- Kochen-Specker n = 18: Unsatisfiable combinatorial problem instance evaluated in dimension 6.
- SMS (
smsg): SAT-modulo-symmetries solver capable of emitting LRAT derivation chains and external symmetry clauses. - LRAT: Linear Resolution Asymmetric Tautology certificate format for linear-time UNSAT verification.
lrat-check: Standalone certificate checker atlrat-check.
Method
The verification pipeline was tested by running smsg -v 18 --lrat-output. The solver returned UNSAT in 35 s, producing a 530 MB LRAT certificate and d6n18_symclauses.json, a JSON list containing permutation-justified symmetry-breaking clauses generated by --sym-break-clauses.
Passing the certificate directly to lrat-check caused the checker to halt at line 0 without validating derivations. Execution records and outputs were preserved in d6n18_sms.log, d6n18_symclauses.json, and frontier/ks6/cert/d6n18_sms.lratcheck.log.
Discussion
Standalone SMS LRAT certificate validation for Kochen-Specker n = 18 on this build is proved dead. Derivations in the linear trace depend on external symmetry clauses, but lrat-check cannot parse or compose with the detached JSON artifact.
The underlying UNSAT result remains intact. However, standalone SMS LRAT generation cannot operate as a self-contained proof pipeline. Workflows requiring verifiable proofs must bypass SMS standalone LRAT generation on this build and instead generate a plain-solver DRAT cover across a symmetric case split, as in MF-184.
For everyone — the takeaway
What this means
Solvers often speed up searches by pruning symmetric copies of a configuration. When a solver logs these symmetry steps in an external file instead of the certificate itself, standard proof checkers cannot verify the run. For Kochen-Specker n = 18, standalone SMS LRAT files fail validation; generating verifiable proofs requires plain DRAT traces split across symmetric cases.
Attribution and prior art
Register references
- Register entry: ML-098
- Related register entries: MF-184
- Receipt artifacts:
frontier/ks6/cert/d6n18_sms.lratcheck.logd6n18_sms.logd6n18_symclauses.json- Prior art: No prior-art position stated.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 0 of 3 receipt files bundled (1 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.