pub fn decide_laddered(
num_vars: usize,
clauses: &[Vec<Lit>],
) -> (bool, LadderStats)Expand description
Ladder up the hypercube: crush what we can, brute-force the rest. Branch-and-cut over {0,1}ⁿ,
one variable at a time — exactly DPLL with our certified cuts as the theory:
- base — a residual empty clause means this subcube is fully covered (UNSAT branch); no residual clauses means a corner escapes here (SAT).
- unit propagation — a residual unit clause forces its variable (free dimension reduction).
- cut — try the certified shadows (counting / parity / cutting-planes) on the residual; if one fires, the whole subcube is crushed without descending — the learned invariant doing its work.
- branch — otherwise split on a residual variable and ladder down.
Structured families (pigeonhole, Tseitin, clique) are crushed by a cut at or near the root in a
handful of nodes at any n, because the cut is scale-free; the genuinely unstructured residual is
brute-forced by the branching. Works on raw clauses, so it ladders past the cube’s 63-variable
geometric ceiling.