Finding the Hardest Formulas for Resolution (Extended Abstract)

Tomás Peitl, Stefan SzeiderIJCAI 2021 · DOI

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:

  1. Candidate Filtering and Symmetry Breaking: The search was restricted to Saturated Minimally Unsatisfiable (SMU) formulas. Using the Nauty graph 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.
Bipartite graph representation of a simple formula where $V_1$ represents literals and $V_2$ represents clauses.
  1. 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.

The three hardest formulas for $m=10$ clauses, each requiring a resolution proof of 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

BibTeX
@inproceedings{peitl2021finding,
  author = {Tomás Peitl and Stefan Szeider},
  title = {{Finding the Hardest Formulas for Resolution (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/657},
}
Figure