🤖 AI

How To Discover Short, Shorter, and the Shortest Proofs of Unsatisfiability: A Branch-and-Bound Approach for Resolution Proof Length Minimization

This paper introduces a novel branch-and-bound algorithm utilizing a symmetry-breaking layer list representation and advanced pruning techniques to significantly minimize resolution proof lengths, outperforming state-of-the-art solvers by reducing proof sizes by 25–60% and solving twice as many instances for finding the shortest unsatisfiability proofs.

Original authors: Konstantin Sidorov, Koos van der Linden, Gonçalo Homem de Almeida Correia, Mathijs de Weerdt, Emir Demirović

Published 2026-08-26

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Konstantin Sidorov, Koos van der Linden, Gonçalo Homem de Almeida Correia, Mathijs de Weerdt, Emir Demirović

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of modern computing, software often acts as a tireless logician, checking whether a complex set of rules can ever be satisfied simultaneously. This process, known as propositional satisfiability, is the engine behind everything from verifying the safety of microchips to planning the movements of autonomous robots. When a computer program finds that a set of rules contains a contradiction—meaning no possible arrangement of facts can make them all true—it declares the problem "unsatisfiable." For decades, the primary goal of researchers in this field has been to find a solution quickly. However, a new question has emerged: if a computer says a problem is impossible, how can we be absolutely sure it is right? The answer lies in a justification, a step-by-step chain of logic that proves the impossibility beyond any doubt. This chain is called a proof. While modern computers are incredibly fast at finding these proofs, they are not always efficient at finding the shortest ones. A proof that is unnecessarily long is like a map that takes a traveler on a winding, scenic route when a straight path exists; it gets the job done, but it wastes time and resources, and in high-stakes verification, a shorter proof is easier to check and trust.

A team of researchers at Delft University of Technology has developed a new method to hunt down these shortest possible proofs. Their work addresses a specific frustration: while current software can generate a valid proof of unsatisfiability in seconds, that proof might be far longer than necessary. In fact, for many standard test problems, the proofs generated by the best existing software were found to be at least fifty percent longer than the absolute shortest proof available. The researchers realized that finding the shortest proof is not just a matter of running the existing software faster; it is a distinct optimization problem, akin to searching for the single most efficient path through a vast, foggy maze. The challenge is that the number of possible paths is so enormous that checking them one by one is impossible. The team's breakthrough was to invent a new way of organizing these paths to eliminate redundant searches and to create a system that could prune away dead ends before they were fully explored.

The core of their innovation is a new way of representing the proof itself, which they call a "layer list." Imagine the proof as a construction project where new facts are built upon old ones. Traditional methods often get confused by the order in which these facts are added, treating two identical sets of facts as different problems simply because they were assembled in a different sequence. This creates a massive amount of unnecessary repetition in the search. The new layer list method groups these facts by their "level of indirection," essentially organizing them into layers based on how many steps of logic are required to derive them. This structure breaks all the confusing symmetries that previously slowed down the search, ensuring that the computer only looks at each unique set of facts once. By organizing the search this way, the researchers could design a "branch-and-bound" algorithm. This is a systematic strategy where the computer explores different branches of the proof tree but immediately stops exploring a branch if it calculates that the path will inevitably be longer than a solution it has already found.

To make this search even more efficient, the team introduced several pruning techniques, or rules for cutting off unproductive paths. One such rule involves identifying "frontier" clauses, which are the most essential facts in the current set of rules. The researchers proved that any proof can be rewritten using only these essential facts without making the proof longer. If a potential proof step relies on a non-essential fact that is already covered by a stronger, more essential fact, the algorithm discards that step immediately. Another powerful tool is a "dominance" check, where the computer compares the current state of the search against states it has visited before. If the current path is clearly worse than a path already explored—meaning it uses more steps or fewer essential facts—the computer abandons it. Finally, they established a mathematical lower bound, a minimum possible length for any proof, based on the smallest subset of rules that creates the contradiction. If the current search path cannot possibly beat this minimum, the algorithm stops wasting time on it.

When the researchers tested this new approach, the results were significant. On a collection of standard test problems from a 2002 competition, their method reduced the length of proofs generated by state-of-the-art software by thirty to sixty percent. On smaller, synthetic formulas, the reduction was between twenty-five and fifty percent. In many cases, the proofs were cut in half. Furthermore, when the goal was to find the absolute shortest proof and prove that no shorter one exists, their method solved twice as many problems as the previous best approach and did so orders of magnitude faster. For the problems both methods could solve, the new approach was dramatically quicker, often finishing in seconds what took the older method hours. However, the researchers also identified a limit to their success. The method works consistently well until the proofs become extremely large, specifically when they exceed one million steps. At that scale, the memory required to store the proof structure becomes too great for current computers to handle, causing the process to crash.

This work does not claim to make the original software that finds proofs obsolete; rather, it offers a powerful tool to refine the output of those systems. The researchers emphasize that while shorter proofs are generally faster to verify, a shorter proof does not automatically mean the original software ran faster to find it. The goal of this new method is to provide a cleaner, more efficient justification for why a problem has no solution. By stripping away the redundant steps and focusing on the most direct logical path, the team has provided a way to make the reasoning of artificial intelligence more transparent and trustworthy. Their findings suggest that for many problems, the "room for improvement" in proof length is substantial, and that by changing how we organize the search for these proofs, we can uncover solutions that were always there, just hidden behind layers of unnecessary complexity.

Technical Summary: Discovering Short, Shorter, and the Shortest Proofs of UNSAT Formulas

Problem Statement

Modern SAT solvers are powerful tools capable of determining the satisfiability of propositional formulas and generating resolution proofs for unsatisfiable (UNSAT) instances. These proofs are essential for verification, ensuring that the solver's "UNSAT" claim is correct. However, while modern solvers like CaDiCaL empirically produce relatively short proofs, there is no guarantee that these are the shortest possible proofs.

The problem of finding the shortest resolution proof is an optimization problem where the feasible set is the set of all valid proofs for a given formula, and the objective is to minimize the proof length (number of clauses). This problem is significantly harder than simply finding a valid proof, as the search space is exponentially large and highly symmetric. Previous work, such as Peitl and Szeider (2021), attempted to solve this via SAT encodings but was limited to very small formulas (up to ~12 clauses) due to the explosion of the search space and incomplete symmetry breaking.

Methodology

The authors propose a novel branch-and-bound algorithm designed to enumerate resolution proofs and find the shortest one. The core of their methodology relies on three main components: a new proof representation, a specific branching strategy, and advanced pruning techniques.

1. Layer List Representation

To address the issue of permutation symmetries (where reordering clauses creates different but equivalent proofs), the authors introduce a layer list representation $(L_0, L_1, \dots, L_n)$ .

Structure: $L_0$ contains the axioms (original formula clauses). Each subsequent layer $L_j$ contains clauses derived by resolving a clause from the immediately preceding layer ( $L_{j-1}$ ) with a clause from any earlier layer ( $L_0 \cup \dots \cup L_{j-1}$ ).
Take-it-or-leave-it Property: A crucial constraint mandates that if a clause can be derived in an earlier layer, it must be placed there. This prevents a clause from appearing in a later layer if it could have been derived earlier.
Uniqueness: Theorem 2 proves that for any set of clauses constituting a proof, there is exactly one canonical layer list representation. This representation breaks all symmetries stemming from clause permutations, unlike previous DAG-based encodings which could represent the same set of clauses with different topological orderings.

2. Branch-and-Bound Search

The algorithm treats the construction of a layer list as a recursive search over subproblems.

Subproblem Definition: A subproblem $P$ tracks Previous (clauses from layers $0$ to $k-1$ ), Current (clauses in layer $k$ ), Next (candidate clauses for layer $k+1$ ), and Forgotten (clauses that could have been derived earlier but were not included).
Partitioning: Instead of enumerating all subsets of resolvents, the algorithm branches on individual candidate clauses for the next layer. It decides whether to include a candidate clause in the Next layer or move it to the Forgotten set, effectively exploring the space of valid layer lists.

3. Pruning and Optimization

The search is guided by several pruning procedures to eliminate non-optimal branches:

Frontier Pruning: The algorithm restricts derivations to "frontier" clauses (clauses not subsumed by other known clauses). Theorem 3 establishes that any proof using non-frontier clauses can be transformed into a proof using only frontier clauses without increasing the length.
Dominance Pruning: A dominance relation is defined between subproblems. If subproblem $P'$ dominates $P$ (meaning $P'$ has used fewer or equal axioms, can derive a superset of clauses, has a superset of frontiers, and has forgotten a subset of clauses), then any proof recoverable from $P$ can also be recovered from $P'$ with equal or better length. Dominated subproblems are discarded.
Lower Bounding: The algorithm uses the size of the Smallest Minimal Unsatisfiable Subset (SMUS) to estimate a lower bound on the remaining proof length. Specifically, it leverages the fact that a proof for a minimally unsatisfiable formula with $m$ clauses requires at least $2m-1$ steps. This bound is generalized for non-minimal formulas using SMUS calculations (approximated via the Forqes package or a custom branch-and-bound routine).

Key Contributions

Layer List Representation: A novel proof encoding that uniquely maps any set of proof clauses to a single structure, breaking all permutation symmetries and improving upon state-of-the-art DAG-based symmetry breaking.
Branch-and-Bound Algorithm: A complete search procedure that operates on layer list prefixes, capable of finding the optimal (shortest) resolution proof.
Pruning Mechanisms: A suite of pruning techniques including frontier-based simplification, dominance relations on subproblems, and SMUS-based lower bounding.
Anytime Capability: The algorithm functions as an anytime optimizer, providing valid upper bounds (shorter proofs found so far) and lower bounds throughout the search.

Experimental Results

The authors evaluated their approach on two datasets: synthetic formulas (e.g., Pigeonhole, Parity, Random 3-CNF) and UNSAT instances from the SAT Competition 2002.

Proof Length Reduction:
- On synthetic formulas, the approach reduced proof lengths by 25% to 50% compared to CaDiCaL.
- On SAT Competition 2002 instances, proofs were shortened by 30% to 60%.
- In specific cases (e.g., subset cardinality formulas), reductions of at least 40% were consistently observed.
Optimality and Speed:
- Compared to the baseline approach by Peitl and Szeider (2021), the proposed method solved twice as many instances to optimality.
- For instances solved by both, the proposed approach reduced the time to optimality by orders of magnitude (e.g., solving 9-clause formulas in seconds vs. thousands of seconds for the baseline).
- The method successfully computed resolution hardness numbers ( $h_m$ ) for formulas up to 8 clauses and partially for 9 clauses, significantly outperforming the baseline in execution time.
Limitations:
- The approach is memory-intensive. It encounters out-of-memory errors when the CaDiCaL proof length exceeds approximately $10^6$ steps, as the algorithm must unpack and store large resolution proofs to analyze them.
- The lower bound pruning is limited by the SMUS calculation; for certain formulas (like Pigeonhole), the bound is not tight enough to prune the search effectively.

Significance

The paper claims that its primary significance lies in demonstrating that the proofs generated by state-of-the-art SAT solvers are often far from optimal and that these proofs can be systematically shortened. By introducing a symmetry-breaking representation and an efficient branch-and-bound search, the authors provide a method to:

Verify Solver Efficiency: Estimate the "room for improvement" in solver steps, revealing that standard solvers may take 50% to 200% more steps than necessary.
Optimize Proof Systems: Offer a workflow for proof minimization that is scalable to larger formulas than previous exact methods.
Advance Proof Complexity: Provide a practical tool for computing resolution hardness numbers and exploring the structure of minimal proofs, which has implications for understanding the inherent complexity of propositional logic problems.

The authors conclude that while their approach has memory limitations for very large proofs, it represents a substantial step forward in the automated discovery of optimal resolution proofs, solving more instances faster than previous SAT-encoding approaches.