##  [Resolution Complexity](/resolution-complexity-0) 

 Definition

A quantitative measure of the resources required to produce refutations in the propositional resolution proof system, typically quantified by parameters such as proof length (number of derived clauses), width (maximum clause size), and space (memory measured by simultaneously stored clauses).

 

 

 

 

 

 





## Principle

Principle

Resolution complexity organizes hardness by tracking how restrictions on proof resources force longer or wider refutations; trade-offs between length, width, and space determine the difficulty of refuting unsatisfiable formulas in resolution.

 

 

 

 

 





## Demonstration

Demonstration

Concrete example: propositional encodings of the pigeonhole principle admit only resolution refutations whose length grows exponentially in the number of pigeons; width lower bounds can be used to prove corresponding length lower bounds for that family of formulas.

 

 

 

 

## Misapplication

Misapplication

Treating resolution complexity as equivalent to general algorithmic time complexity or assuming lower bounds in resolution immediately transfer to arbitrary proof systems or SAT solvers without considering simulation relations and heuristics.

 

 

 

 

 





## Consequence

Consequence

Correct application yields rigorous lower bounds on proof search, explains why SAT solvers struggle on particular families of formulas, and guides the design of proof systems and heuristics by revealing which resource is the bottleneck.

 

 

 

 

## Reversal

Reversal

Invert the perspective by asking which formulas admit short, narrow, and low-space resolution refutations; the reversal highlights tractable subclasses and constructive proof strategies rather than hardness.

 

 

 

 

 





## Boundary

Boundary

Applies specifically to the propositional resolution proof system (and closely related clause-learning procedures); it does not directly measure proofs in sequent calculi, Frege systems, or semantic refutations unless explicit simulations are established.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Competes with the broader notion of proof complexity (which spans many proof systems) and with syntactic measures like circuit size; resolution complexity is narrower but often more amenable to combinatorial lower-bound techniques.

 

 

 

 

 





## Synthesis

Synthesis

Resolution complexity is the set of quantitative parameters (length, width, space) that characterize the cost of deriving contradictions in resolution; by studying trade-offs among these parameters one obtains precise explanations of propositional hardness and guidance for solver design.