Research · Papers · The SHA-256 record and exact synthesis · ML-074
Method limit of cube-and-conquer without algebraic reduction
march_cu on c=3/p=8 yielded 4096 cubes timing out at 600 s; algebraic reduction enables 0.4-6 s decisions.
Published 2026-09-04
For everyone
Plain summary
When search problems are large and complex, logic solvers often split them into thousands of smaller pieces to solve them individually. This entry shows where that strategy breaks down. On an unsimplified math problem (the c=3 / p=8 seam problem), splitting it into 4,096 sub-cases caused every single sub-case to hit a 600-second timeout without resolving anything, heading for over 91 hours of wasted runtime before we stopped it. In contrast, simplifying the problem first with mathematical rules let the sub-cases finish in 0.4 to 6 seconds each. Three quick algebraic checks settled in seconds what four large solver runs could not. Automated splitting cannot replace algebraic simplification; it works only after the math is already trimmed down.
Result
Applying cube-and-conquer directly to the unreduced c=3 / p=8 seam instance yields no decision. march_cu partitions the raw formulation into 4,096 cubes in 84 s, but downstream evaluation produces 0 SAT and 0 UNSAT outcomes, with all tested cubes timing out at 600 s.
Conversely, applying quotient-prefix reduction before partitioning shrinks the residual search space so that individual cubes decide within 0.4 s to 6 s (tested on the p5 cell). Cube-and-conquer amplifies an existing algebraic reduction; it does not substitute for invariant reduction on structured seam instances.
Setting and definitions
The setting covers exact synthesis and satisfiability search over structured algebraic seam instances, parameterized by configurations such as c=3 / p=8 and the p5 cell.
- Cube-and-conquer: lookahead partitioning (via march_cu) that emits branch assignments (cubes), followed by conflict-driven clause learning solvers on the subproblems.
- Quotient-prefix reduction: algebraic factoring of invariant prefixes and structural redundancies before generating propositional encodings.
- Seam instance: structured constraint satisfaction problem arising across parameter boundaries in exact synthesis.
Method
Solver runs recorded in artifact RECORD-WIDER-SEAM-PROGRESS.log:
- Unreduced partitioning: march_cu split the raw c=3 / p=8 seam instance into 4,096 cubes in 84 s of lookahead time.
- Direct evaluation: sequential solving on the cubes applied a 600 s cutoff per cube. The first 75 cubes reached the 600 s limit with 0 SAT and 0 UNSAT certificates, projecting roughly 91 hours of runtime before early termination.
- Comparative reduced evaluation: quotient-prefix reduction removed structural invariants on the p5 cell formulation before partitioning. Each resulting cube finished in 0.4 s to 6 s.
- Algebraic verification: three lightweight algebraic tests decided in seconds the structural feasibility questions that four solver campaigns failed to settle.
Discussion
Increasing lookahead splitting depth or raw compute does not compensate for missing invariant reductions in structured algebraic spaces. Across four campaigns on unreduced formulations, solvers timed out, while cheap algebraic tests resolved the underlying structure immediately.
Cube-and-conquer remains effective on structured domains only when lookahead partitioning operates on the residual space produced by quotient-prefix simplification.
For everyone — the takeaway
What this means
Solvers cannot replace mathematical simplification. Splitting an unsimplified algebraic problem into thousands of cases just yields thousands of cases that time out. Four large solver campaigns produced nothing on raw formulas, while simple math checks settled the questions in seconds. Solvers multiply the power of mathematical reductions; they do not remove the need to find structural invariants first.
Register references
- ML-074
- Receipt:
RECORD-WIDER-SEAM-PROGRESS.log
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 1 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-04
- 2026-09-04Published on this site.