Abstract
This paper introduces and computes the first ten resolution hardness numbers—the exact length of the shortest possible proof for the "hardest" propositional formulas with a fixed number of clauses. By combining advanced symmetry-breaking techniques with a novel SAT-based "meta-solver," the authors move beyond theoretical asymptotics to provide a concrete map of the most difficult challenges for modern automated reasoning.
Introduction
In the world of logic and computer science, the Resolution proof system is the backbone of most modern SAT solvers. While it is well-understood that certain problems are "hard" for resolution—meaning their shortest proof is exponentially long—this hardness is typically discussed in vague, asymptotic terms. This research addresses a more precise question: For a fixed number of clauses $m$, what is the absolute maximum number of steps required to prove a formula is unsatisfiable? This value is defined as the resolution hardness number, $h_m$.
Finding these numbers presents a massive combinatorial challenge. The space of possible formulas is astronomical, and determining the shortest proof for even a single formula is itself a computationally difficult task.
Methodology
The researchers employed a two-pronged strategy to make this search feasible:
- Candidate Filtering and Symmetry Breaking: The search was restricted to Saturated Minimally Unsatisfiable (SMU) formulas. Using the
Nautygraph symmetry package, the authors generated these formulas modulo isomorphism, preventing redundant checks of renamed versions of the same formula. Formulas are often represented as bipartite graphs to facilitate this analysis.
- Efficient SAT Encoding ($short_s(F)$): To find the shortest proof of a specific candidate formula $F$, a "SAT for SAT" approach was developed. A new encoding allows a SAT solver to determine if a resolution proof of length $s$ exists. By iteratively increasing $s$, the exact resolution complexity can be pinpointed. Symmetry-breaking within the proof search itself further optimized this process.
Key Results
The authors successfully computed the first ten resolution hardness numbers ($h_m$): 1, 3, 5, 7, 10, 13, 16, 19, 22, and 26.
The $m=10$ Phase Transition
A significant discovery occurred at $m=10$. While for smaller $m$, formulas with a "deficiency" (the difference between clauses and variables) of 1 or 2 were the hardest, at $m=10$, a phase transition was observed where formulas with a deficiency of 4 became the most difficult. There are exactly three "hardest" formulas for $m=10$ (modulo isomorphism), each requiring 26 steps.
Discussion and Insights
The results suggest that Regular SMU formulas—where every literal appears at least twice and adding any literal would make the formula satisfiable—are the primary drivers of hardness. This work demonstrates the power of "meta-solving," using SAT solvers to reason about the fundamental limits of SAT solvers themselves. By providing concrete data points, the study confirms that $h_m$ grows faster than any polynomial, supporting Haken’s 1985 theoretical lower bounds with empirical evidence.
Limitations and Future Work
Computational scaling remains the primary hurdle; computing $h_{11}$ or $h_{12}$ would require a significant leap in filtering or encoding efficiency. Additionally, while the hardest formulas found were always "regular," proving this "Regularity Conjecture" for all $m$ remains an open theoretical challenge. Finally, the precise computational complexity of the SHORT(F, s) problem continues to be a subject of debate in the field.
Summary updated