Resolution Proof Compression by Splitting¶
A post-processing algorithm that splits a resolution refutation on a chosen variable into complementary branch proofs, recombines them by resolution, and retains the result when it reduces proof size.
Core Idea¶
Resolution proof compression by splitting transforms a completed resolution refutation rather than changing the search that found it. Given a proof DAG ending in the empty clause and a selected variable x, the algorithm constructs one transformed branch that derives x and another that derives not-x. Resolving those two branch conclusions recovers the empty clause, preserving the refutation while reorganizing shared and duplicated subproofs.
Scope of Application¶
- Proof logging pipelines. A solver's resolution refutation is compressed after generation before storage, checking, or interpolation.
- Certified unsatisfiability. The transformed DAG preserves an empty-clause derivation that can be independently checked.
- Heuristic minimization. Several pivots can be attempted under time and memory limits with rollback to the best proof.
- Proof-complexity experiments. Researchers compare node, edge, or serialized size while keeping the metric explicit.
Clarity¶
A description should state the input proof representation, pivot variable, branch-map rules, handling of shared DAG nodes, recombination step, and size metric. 'Split the proof' is insufficient if it does not explain how each original inference becomes a valid inference or bypass in each branch. Compression by node count can differ from compression by literal count or file size, so the objective must be fixed before comparison.
Manages Complexity¶
The transformation can expose a repeated variable-dependent structure and replace it with two cleaner conditional derivations plus one recombination. That can shrink a tangled DAG, but branch duplication can also destroy sharing. The best-so-far rollback makes the iterative procedure monotone in retained proof size even though individual transformations are not.
Abstract Reasoning¶
- Validate the input as a resolution DAG with an empty-clause sink.
- Choose a candidate variable, optionally using the proof's pivot additivity profile.
- Construct both literal-indexed proof maps while preserving valid inputs and resolution steps.
- Evaluate the maps at the empty-clause node to obtain complementary branch conclusions.
- Resolve the branch roots and check the resulting refutation independently.
Knowledge Transfer¶
The algorithm transfers among resolution proofs that expose pivots and DAG structure compatible with its maps. A proof system with different inference rules needs a new soundness argument; a generic divide-and-conquer optimization is not this method. The broader lesson—condition on a variable, simplify branches, recombine, and retain only improvement—can inspire other transformations without inheriting the name.
Relationships to Other Abstractions¶
Current abstraction Resolution Proof Compression by Splitting Domain-specific
Parents (1) — more general patterns this builds on
-
Resolution Proof Compression by Splitting is a kind of Compression Prime
Resolution-Proof Compression by Splitting is Compression that rewrites a refutation into complementary variable branches and retains the recombination only when proof size falls.
Hierarchy paths (3) — routes to 3 parentless roots
- Resolution Proof Compression by Splitting → Compression → Abstraction
- Resolution Proof Compression by Splitting → Compression → Optimization
- Resolution Proof Compression by Splitting → Compression → Aggregation → Micro Macro Linkage
Neighborhood in Abstraction Space¶
Resolution Proof Compression by Splitting sits in a sparse region of the domain-specific corpus (63rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Logical Connectives & Formal Systems (13 abstractions)
Nearest neighbors
- Decision Tree Model — 0.85
- Planar SAT — 0.85
- Constructive Logic — 0.84
- Logical or — 0.84
- SATPlan — 0.84
Computed from structural-signature embeddings · 2026-10-08