Research · Papers · Exact answers in open problems · ML-092
Solver wall in SAT-based exact median network synthesis
Optimal median network size undecided for n ≥ 8; SAT solver times out on n=8 at 15, n=9 at 18, n=10 at 21, and n=11 at 24 comparators
Published 2026-09-06
For everyone
Plain summary
A median network is a fixed circuit composed of two-input comparison units (comparators) that selects the middle value from a set of inputs. Determining the absolute minimum number of comparators needed to find the median is a fundamental problem in circuit design. For sets of eight or more inputs, this minimum size remains completely unknown.
Researchers attempted to resolve these minimums using Boolean satisfiability (SAT) solvers—automated search programs that determine whether a mathematical formula has a valid solution or prove that none exists. For eight or more inputs, the solvers hit a computational wall: they time out before proving that smaller networks are impossible. Crucially, an earlier published result by Smith (1996) claiming an optimal size for nine inputs could not be reproduced. In addition, an internal prefix-census metric reported in preliminary testing logs was determined to be broken due to incomplete relabelling and must not be used.
Result
The optimal size of a median network remains undecided for all input sizes n ≥ 8. Comparator-sequence SAT encodings with lex-minimal normal form and cone constraints fail to refute the UNSAT side within practical limits. Specifically:
- n = 8 at 15 comparators: kissat and CaDiCaL time out at 3600 s with DRAT proofs exceeding 6.5 GB.
- n = 9 at 18 comparators (calibration cell): kissat and CaDiCaL time out at 3600 s with DRAT proofs exceeding 6.5 GB.
- n = 10 at 21 comparators: kissat and CaDiCaL time out at 3600 s.
- n = 11 at 24 comparators: kissat and CaDiCaL time out at 3600 s.
Consequently, the published optimality claim for n = 9 (Smith 1996) is not reproduced.
Setting and definitions
A median network on n inputs is an oblivious sequence of comparator operations that routes the median element to a designated output channel. In SAT-based exact synthesis, network existence at a given size bound is encoded into propositional logic over comparator wire pairs and routing permutations. Symmetry reduction is enforced using lex-minimal normal form conditions alongside structural cone constraints. Refutations are validated via DRAT proof certificates emitted by CDCL solvers.
Method
Exact size existence queries were formulated using comparator-sequence encodings, lex-minimal normal form symmetry breaking, and cone constraints. Verification runs were executed using the SAT solvers kissat and CaDiCaL with a 3600 s timeout per instance. Proof streams were logged to DRAT format files.
The execution data and verification receipts are recorded in:
frontier/median/PROGRESS.box.logruns/*.status.jsonlane WALL.md
Discussion
The direct comparator-sequence SAT encoding experiences exponential proof growth and solver timeouts across all test cases where n ≥ 8. For n = 8 at 15 comparators, n = 9 at 18 comparators, n = 10 at 21 comparators, and n = 11 at 24 comparators, neither kissat nor CaDiCaL resolves the UNSAT side within 3600 s, generating DRAT proofs that expand past 6.5 GB before termination.
This failure of refutation leaves the optimal comparator count unresolved for n ≥ 8. In particular, the n = 9 optimality claim published by Smith (1996) could not be verified or reproduced under this framework.
A specific defect is noted in the receipts: the prefix-census count presented in the WALL.md lane report is broken because its canonicalisation procedure evaluated an incomplete set of relabellings; this count must not be cited.
As an untried alternative to pure SAT encodings, the register notes the possibility of adopting a generate-and-prune architecture featuring labelled-output subsumption derived from the sorting-network literature.
For everyone — the takeaway
What this means
Proving the exact minimal complexity of median-filtering networks remains stalled at eight inputs. Modern automated reasoning tools cannot exhaust the search space required to rule out smaller designs, generating massive proof files before timing out. Because earlier published baselines for nine inputs could not be confirmed, the true theoretical limits of median networks are wider open than previously thought. Pushing past this computational barrier will require shifting from monolithic SAT formulations to specialized pruning and subsumption techniques.
Attribution and prior art
Prior art: A verification check was unable to reproduce the published n = 9 optimality claim from Smith (1996). Sources: Dobbelaere, median networks table
Register references
- ML-092
frontier/median/PROGRESS.box.logruns/*.status.jsonlane WALL.md- Smith (1996)
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 3 of 3 receipt files bundled (4 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.