Research · Papers · Exact answers in open problems · ML-094
Exact B2 circuit size of MOD3 on 6 inputs and solver scaling wall
C_B2(MOD3,0 on 6 inputs) conjectured 12; deciding 11 gates timed out at 5400 s with UNSAT cost growing 30-100x per gate
Published 2026-09-06
For everyone
Plain summary
Boolean circuit minimization finds the smallest number of two-input logic gates needed to compute a given logic function. For the MOD3,0 function on 6 inputs, which checks whether the sum of six bits is divisible by 3, Knuth conjectured that exactly 12 gates are required. Proving this requires showing that no 11-gate circuit can compute the function. Automated SAT solvers attempt this proof by ruling out every possible 11-gate design. In testing, the 11-gate target timed out at 5400 seconds across multiple solvers, generating proof logs between 3.4 and 7.7 gigabytes before stopping. Because search runtime multiplies by 30 to 100 times for each added gate, the exact minimum circuit size for MOD3 on 6 inputs remains undecided.
Result
The exact circuit size C_B2(MOD3,0 on 6 inputs) remains undecided. Knuth's conjecture predicts C_B2(MOD3,0 on 6 inputs) = 12. Verifying C_B2(MOD3,0 on 6 inputs) ≥ 12 requires establishing the unsatisfiability of the 11-gate synthesis formulation, which timed out at 5400 s across multiple SAT solvers. The empirical UNSAT runtime scales by 30x to 100x per gate rung, leaving the s = 11 target approximately three rungs beyond the last closed verification instance.
Setting and definitions
Let B2 denote the basis of all Boolean functions on two inputs. For a Boolean function f: {0,1}^n → {0,1}, the exact circuit size C_B2(f) is the minimal number of gates from B2 required to compute f. The function MOD3,0 on n inputs evaluates to 1 if and only if the sum of its n inputs is congruent to 0 mod 3.
Exact synthesis encodes the existence of a size-s circuit computing f into a propositional satisfiability (SAT) formula. A refutation certificate is recorded as a DRAT (Deletion Resolution Asymmetric Tautology) proof stream.
Method
Exact synthesis instances for MOD3,0 on 6 inputs were evaluated across gate sizes s under two SAT solvers:
- s = 6: 3 s
- s = 7: 24 s
- s = 8: 668 s
- s = 11: timed out at 5400 s on both solvers.
At s = 11, solvers emitted DRAT certificate streams reaching 3.4 GB to 7.7 GB before hitting the timeout.
A calibration instance on n = 5 inputs at s = 9 gates timed out at 1500 s. First-gate orbit cube decomposition applied to this calibration cell resolved only 1 of 4 cubes. An untried route proposes topology-family partitioning across 40 or more cores with per-shape DRAT streams and an explicit cover receipt, targeting validation on the n = 5 calibration cell first.
Run records are logged in frontier/mod3/STATUS.log, runs/*.status, and WALL.md.
Discussion
Monolithic SAT solver runs cannot bridge the gap to s = 11 under the observed 30x to 100x per-gate scaling, leaving C_B2(MOD3,0 on 6 inputs) and Knuth's conjecture open.
The partial resolution on the n = 5, s = 9 calibration instance shows that simple first-gate orbit cube partitioning cannot clear the search space. The data establishes a practical barrier for monolithic exact synthesis on this domain, while leaving open distributed topology-family partitioning over parallel clusters.
For everyone — the takeaway
What this means
This entry shows the practical limits of automated logic synthesis solvers on exact circuit bounds. Even for a function with six inputs, proving that no smaller circuit exists requires exploring a search space that multiplies up to 100-fold with each added gate. Single-solver runs cannot reach the 11-gate threshold needed to test Knuth's conjecture on 6 inputs. Resolving the bound will require parallel strategies that partition the search space across circuit topology families.
Attribution and prior art
Prior art: Knuth's conjecture predicts a circuit size of 12 for MOD3,0 on 6 inputs. Sources: Kulikov, Pechenev, Slezkin 2022 (MFCS)
Register references
- ML-094
- Receipt:
frontier/mod3/STATUS.log - Receipt:
runs/*.status - Receipt:
WALL.md - Prior art: Knuth's conjecture predicts a circuit size of 12 for MOD3,0 on 6 inputs.
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 1 of 2 receipt files bundled (3 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.