The maximal amount of memory-like resource required during a proof or refutation, often formalized as the maximum number of formulas, clauses, or proof lines that must be simultaneously kept in memory under a specified proof model.

Principle

Captures concurrent storage requirements: proof space measures how many intermediate items must be retained at peak, reflecting memory bottlenecks independent of total steps.

Demonstration

In clause-space models for resolution, proof space counts the largest number of clauses that a refutation algorithm must keep stored at any time; pebbling arguments often illustrate lower bounds on proof space.

Misapplication

Confusing proof space with total memory footprint of an implementation (which includes data structures, indices, caching) or with search tree size leads to mistaken resource planning; space is a model-dependent abstract metric.

Consequence

High lower bounds on proof space show inherent memory difficulty for refutation in the model and motivate space-saving strategies (e.g., clause deletion schedules, resumable proofs) or different proof systems.

Reversal

Instead of peak concurrent items, one can measure cumulative memory-time product (integral of memory over time) to capture total memory usage over the entire proof, which flips focus from peak to aggregate cost.

Boundary

Depends on the chosen space model (clause space, variable space, formula-space) and on assumptions about what constitutes storage and whether reuse or compression is allowed; it excludes non-memory resources like CPU time unless combined.

Semantic Tension

In tension with length and width: proofs that are short may still demand large space, and minimizing space can force longer proofs; space formalizes a different axis of complexity than sequential steps or clause size.

Synthesis

Proof space is the peak memory requirement metric that, together with length and width, completes a triad of orthogonal complexity measures; understanding space trade-offs informs algorithms, data structures, and choices of proof calculi to manage memory pressure.