The number of inference steps in a formal derivation or proof within a specified proof system; each step is an application of a rule that produces a new formula or sequent from previous ones.

Principle

Counts sequential inferential effort: shorter proofs minimize the number of rule applications required to derive a target formula from premises or axioms under the chosen formal system.

Demonstration

In propositional resolution, proof length is the number of resolution or weakening steps performed until the empty clause (refutation) is derived, regardless of the size of intermediate clauses.

Misapplication

Using proof length across different proof systems or encodings without normalization can mislead — some systems allow many small local steps while others use fewer, more powerful rules, making raw counts incomparable.

Consequence

Lower bounds on proof length establish hardness results for automated provers in that system; finding short proofs enables faster verification and can guide proof search heuristics to prefer concise derivations.

Reversal

One can invert focus to measure symbolic size (proof size measured in total number of symbols or bits) rather than step count, which emphasizes formula complexity per step instead of step count.

Boundary

Defined relative to a specific proof system, choice of primitive rules, and granularity of what counts as a step; it excludes resources like memory usage per step and may not reflect parallel inference.

Semantic Tension

Competes with width and space measures: a proof can be short but wide or space-intensive, so length alone does not capture all dimensions of complexity.

Synthesis

Proof length is a linear measure of inferential work in a formal system; combined with width and space metrics it provides a multi-dimensional picture of proof complexity and informs algorithmic choices about trade-offs between many small steps and fewer complex rules.