Research · Papers · The SHA-256 record and exact synthesis · ML-053
Empirical limits of single-counterexample CEGIS exact synthesis
K=4,n=2,p=1: UNSAT; K=3,n=3,p=2: UNSAT; K=3,n=3,p=3: SAT; K=2,n≤5,p=3: UNSAT
Published 2026-08-29
For everyone
Plain summary
This study measures where a specific circuit-synthesis tool hits an operational wall. Exact synthesis finds a circuit that computes a target function with an exact number of product terms. The tested tool uses CEGIS: it proposes a circuit, checks for an input where the circuit gives the wrong answer, adds that single counterexample to its list, and restarts the solver from scratch.
On 10-input functions (1,024 truth-table rows), the tool finishes in seconds. At 12 inputs or more, every tested run stalled. Several runs timed out after 7,200 seconds, one became inconclusive after 2,888 seconds, and a control known to be solvable timed out after 10,800 seconds. Because the tool times out on a target with a known solution, a timeout reflects search failure, not the nonexistence of a circuit. An alternative full-domain encoder was written and confirmed on a small control. The verdict is CAVEAT because this is a tool boundary, not a circuit lower bound.
Result
For the tested single-counterexample CEGIS instrument, 10-input / 1,024-row instances resolve in seconds:
K=4,n=2,p=1: UNSAT in 0.1 sK=3,n=3,p=2: UNSAT in 4.2 sK=3,n=3,p=3: SAT in 15.6 sK=2,n≤5,p=3: UNSAT in 2.7 s
Every tested instance at 12 inputs or more failed to terminate:
K=4,n=3atp=4: TIMEOUT at 7,200 sK=3,n=4atp=4: TIMEOUT at 7,200 sK=4,n=4atp=7: TIMEOUT at 7,200 sK=5,n=3atp=7: INCONCLUSIVE at 2,888 s (exhausted round budget)- MF-001 tile control at
p=6: TIMEOUT at 10,800 s
The MF-001 tile is known SAT via explicit construction from two verified three-AND carry cells. The timeout on this control confirms that non-terminating runs do not establish UNSAT.
Setting and definitions
Single-counterexample CEGIS tests candidate circuits against a verifier, appends one failing truth-table assignment per round, and solves the augmented formula from scratch. Exact synthesis determines whether a circuit with product count p computes a specified function. Configuration parameters K and n are recorded directly from the ledger without further expansion. A 10-input target has 2¹⁰ = 1,024 truth-table rows. A full-domain encoding instantiates all rows simultaneously instead of discovering them incrementally.
Method
The instrument was benchmarked across the parameter grid preserved in the limits ledger. Solvable small instances and non-returning large instances establish the empirical limit. The MF-001 control provides ground truth: its satisfiability is proven by construction, ruling out UNSAT as the cause of solver non-termination.
The ledger attributes solver stalls past 2¹⁰ domain rows to thrashing caused by incremental single-row accumulation paired with from-scratch solver invocations. The replacement full-domain encoder bypasses incremental refinement and eliminates the MF-018 subset-certificate restriction. It applies circuit-level symmetry breaking via factor commutativity, nonempty factor constraints, and gate-utilization constraints without changing the realisable function set at product count p. On the small control, this encoder settled p=2 (SAT) and p=1 (UNSAT) in under 1 s each.
Discussion
These runs document an empirical boundary: the single-counterexample CEGIS instrument functions reliably near 10 inputs and stalls at 12 inputs or more under the tested parameterisations. It does not establish circuit complexity lower bounds for the unresolved targets. Because the known-SAT MF-001 control timed out at p=6, no timeout from this instrument can serve as an UNSAT certificate.
Curation records state Corrections: NONE, and INDEX lists no corrections for ML-053. The register records no prior-art position. For instances at or above 12 inputs, the recommended path is the AX162 factory encoder using kissat with DRAT proof logging, a pipeline validated to 16 inputs / 65,536 rows. The page verdict is CAVEAT because the findings measure tool divergence rather than mathematical nonexistence.
For everyone — the takeaway
What this means
Don't use this single-counterexample CEGIS tool on functions with 12 or more inputs. It works fast on 10 inputs, but past that point, rebuilding the problem after every single counterexample causes the solver to thrash and time out. When it times out, it doesn't mean your target circuit is impossible; it just means the tool got stuck. For larger synthesis tasks, switch to the AX162 encoder with kissat.
Register references
ML-053
08-multiop-addition-audit\sweep2_results.json
mf001_reaudit_results.json
exact_mc_full.py
mf001_fullencode_results.json
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 4 of 4 receipt files bundled (5 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.