##  [Proof Width](/proof-width-0) 

 Definition

A measure of the maximum syntactic size (for example the number of literals in a clause) of intermediate formulas or clauses that appear in a proof; in resolution proofs it is typically the maximum clause width encountered.

 

 

 

 

 

 





## Principle

Principle

Captures the peak combinatorial complexity of intermediate objects: wider clauses or formulas indicate larger combinatorial combinations of literals that must be handled simultaneously.

 

 

 

 

 





## Demonstration

Demonstration

In resolution-based SAT proofs, the proof width is the largest number of literals found in any clause produced during the refutation; proofs that necessarily generate large-width clauses are often harder to find.

 

 

 

 

## Misapplication

Misapplication

Equating small width with easiness across all systems ignores encoding effects; a low-width proof in one encoding may correspond to a high-width or long proof in another encoding or proof system.

 

 

 

 

 





## Consequence

Consequence

Width lower bounds can be used to prove exponential lower bounds on proof length in resolution; controlling width is a key technique in designing parameterized or fixed-parameter tractable algorithms.

 

 

 

 

## Reversal

Reversal

One may instead consider average width or total symbol count to emphasize overall formula bulk rather than peak width, which shifts attention from worst-case intermediate blow-up to aggregate cost.

 

 

 

 

 





## Boundary

Boundary

Width is tied to the chosen representation (clauses, sequents, formulas) and to what syntactic unit is counted (literals vs atoms vs symbols); it does not directly measure sequential steps or memory unless combined with other metrics.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Competes with proof length and space: narrow proofs can still be long or space-consuming, and small-length proofs can require broad intermediate formulas; width isolates the simultaneous combinatorial demand.

 

 

 

 

 





## Synthesis

Synthesis

Proof width quantifies the maximal simultaneous combinatorial load a proof produces; used alongside length and space it helps predict search bottlenecks and guides transformations or encodings that keep intermediate representations small.