Research · Papers · Symmetry, state encodings and search gauges · MF-018
A soundness condition for subset-UNSAT certificates under symmetry breaking
A subset-UNSAT certificate is sound only when ∀g ∈ G, g(R) = R
Published 2026-08-29
For everyone
Plain summary
An exact-synthesis search can test selected input-output rows when looking for a logic network. A subset-UNSAT certificate is a solver result saying no network satisfies those rows. It can speak for the full problem only when the selected, or cared, rows stay together under every symmetry used to simplify the encoding. A symmetry is a transformation that treats equivalent cases as the same. If it moves a cared row outside the subset, the restricted proof no longer covers the same rows. Four registry certificates were flagged. A later full-domain encoding removes this caveat for that implementation, and the ML-015 symmetry audit found the recovered cared subset invariant under the actual trivial-identity group. The entry is a caveat about certificate soundness. The register does not state a prior-art position.
Result
Let R be the cared-row subset and G the broken symmetry group acting on rows. A subset-UNSAT certificate is sound only when R is setwise invariant under G:
\forall g \in G, g(R) = R.
If this fails, UNSAT for the subset-restricted, symmetry-broken encoding does not certify UNSAT for the intended full problem.
Setting and definitions
R is the set of rows covered by the certificate. G is the group of row transformations introduced by symmetry breaking. g(R) is the image of R under g. Setwise invariance means that this image equals R for every g in G.
Method
BRIEF §B.4.5 records the rule and its application to four registry certificates. The audit identifies R and G, then tests invariance. The register points to ML-015, whose symmetry audit found the recovered cared subset invariant under the actual trivial-identity group.
Discussion
MF-018 is a certificate-soundness condition. It does not classify every subset certificate or decide a named synthesis instance. The limits ledger records that the later full-domain encoding removes this caveat for that implementation because every row is encoded. Other subset encodings still require the audit. No prior-art position is stated. The page verdict is CAVEAT.
For everyone — the takeaway
What this means
A shortcut can simplify a search while changing which cases its proof covers. Selected rows must remain the same set after every allowed relabelling. If one leaves the checked set, the negative result loses support. Researchers can test the condition or encode the full input domain. MF-018 is a practical rule for deciding when a simplified solver certificate can speak for the original problem. It qualifies a method; it does not settle the circuit question. It tells the reader where a proof stops and a full-domain check begins.
Register references
- Entry: MF-018
- Receipt: BRIEF §B.4.5
- Related register reference named in the entry: ML-015
- Prior art: the register does not record this.
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 0 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-08-29
- 2026-08-29Published on this site.