- Atlas
- Computer Science
- Proof Complexity
Proof Complexity
Proof complexity asks a deceptively simple question: when a statement is true, how long must a proof of it be?
9 frameworks, from 1935 to today · Theory Of Computation · Computer Science
- Sequent Calculus and Cut Elimination 1935-Present
- Frege system 1979-Present
- Propositional proof system 1979-Present
- Simulation and Optimality Hierarchy 1979-Present
- Bounded Arithmetic and Propositional Translations 1985-Present
- Resolution 1985-Present
- Algebraic Proof Systems 1990-Present
- Feasible Interpolation 1990-Present
- Probabilistically Checkable and Interactive Proofs 1990-Present
Overview
Proof complexity asks a deceptively simple question: when a statement is true, how long must a proof of it be1? Mathematicians have always cared about whether theorems can be proved, but proof complexity cares about the cost of proving them — the number of lines, symbols, or steps a proof requires1. The field treats proofs as objects of computation, and asks how the resources needed to verify or discover a proof scale with the size of the statement being proved1.
This matters far beyond mathematical aesthetics. If every proof of a certain true statement must be astronomically long in every reasonable proof system, then no computer program — and no mathematician — could ever find one. Proof complexity is the branch of complexity theory that studies exactly this, and it is tied to one of the deepest open problems in all of computer science: whether P equals NP1. A proof system is, in effect, a way of certifying that a statement is true, and the question of whether short proofs always exist is closely connected to whether hard problems can be solved efficiently1.
The 1970s: Proofs as Computational Objects
The field's founding moment came in 1979, when Stephen Cook and Robert Reckhow published a paper asking what it means for a propositional proof system to be "reasonable." Their answer became the field's central definition. A propositional proof system is any efficient (polynomial-time) procedure that checks whether a given string is a valid proof of a given propositional formula1. The formula is a Boolean expression built from variables and the connectives AND, OR, and NOT; a proof is a certificate that the formula is a tautology — true under every assignment of truth values to its variables.
Cook and Reckhow proved a striking theorem: a propositional proof system exists in which every tautology has a short (polynomial-length) proof if and only if NP equals coNP1. Since most researchers believe NP ≠ coNP, this suggests that every proof system must have some tautologies whose shortest proofs are super-polynomially long. The field's task became to prove such lower bounds for specific systems — and to understand which systems are stronger than which.
The same era saw the first major lower bound. In 1985, Armin Haken proved that resolution — a simple proof system in which one derives new clauses by resolving pairs of existing clauses, eliminating one variable at a time — requires exponentially long proofs for a family of formulas encoding the pigeonhole principle: the statement that you cannot fit n+1 pigeons into n holes1. Resolution is the proof system underlying SAT solvers, the programs that decide satisfiability of Boolean formulas, so Haken's result said something practical: certain unsatisfiable formulas will defeat any solver based on clause resolution1.
Resolution and Clause-Based Refutation
Resolution deserves its own place in the story because it is the workhorse of automated reasoning. A clause is a disjunction of literals (a variable or its negation); a formula in conjunctive normal form is a conjunction of clauses. Resolution takes two clauses containing complementary literals — say (x OR A) and (NOT x OR B) — and produces (A OR B). A refutation derives the empty clause, which is unsatisfiable, proving the original formula has no satisfying assignment.
Resolution was introduced in the 1960s by J. A. Robinson as a general-purpose inference rule for automated theorem proving. Its proof complexity, however, was mapped out later. Haken's 1985 lower bound was followed by work showing that resolution is not automatizable in a strong sense — no algorithm can find short resolution proofs efficiently even when they exist — and by refinements such as regular resolution and Davis–Putnam procedures. The connection to SAT solvers made resolution the most practically studied system: every clause-learning solver is, in effect, searching for a resolution refutation, and proof complexity explains why some instances are hard.
Frege Systems and the Depth Hierarchy
The most natural proof system for propositional logic is Frege systems: a finite set of axiom schemes and inference rules, such as modus ponens, that allow you to derive tautologies by ordinary logical reasoning2. Different choices of axioms and rules give different Frege systems, but a foundational result shows they are all polynomially equivalent — each can simulate the other with only polynomial blowup in proof length. This robustness makes "Frege system" a canonical benchmark: proving a super-polynomial lower bound for Frege systems would separate NP from coNP and settle a major open problem. No such bound is known1.
A tractable restriction is bounded-depth Frege, where formulas in the proof are restricted to a fixed number of alternating AND/OR layers. In the late 1980s and 1990s, researchers including Ajtai, and later Pitassi, Beame, and Impagliazzo, proved exponential lower bounds for bounded-depth Frege systems on the pigeonhole principle and related formulas1. These results used sophisticated combinatorial techniques — random restrictions and switching lemmas — and established a genuine hierarchy: more depth means more power, at least for certain formulas.
Algebraic Proof Systems
A parallel tradition treats proofs algebraically. Algebraic proof systems refute unsatisfiable polynomial systems over a field: you derive the constant 1 from the equations by adding multiples of them and multiplying by arbitrary polynomials. The two canonical systems are Polynomial Calculus (work with polynomials directly) and Cutting Planes (work with linear inequalities, allowing addition, multiplication by positive constants, and a division rule). Cutting Planes is especially important because it underlies integer programming solvers and because it can simulate resolution efficiently.
Lower bounds in this world came from connections to algebra and geometry. Polynomial Calculus lower bounds were proved in the late 1990s using degree arguments and linear algebra; Cutting Planes lower bounds followed, often via communication-complexity techniques. The algebraic viewpoint made proof complexity a meeting point for logic, algebra, and combinatorial optimization.
Bounded Arithmetic and Propositional Translations
A third strand connects proof complexity to mathematical logic through bounded arithmetic: formal theories of arithmetic in which quantifiers are restricted to bounded ranges, so that the theories can reason only about feasibly computable objects13. The key discovery, developed by Sam Buss in the mid-1980s and extended by many others, is that bounded arithmetic theories correspond to propositional proof systems via translations: a proof in the arithmetic theory of a statement about all finite structures can be translated into a family of propositional proofs, one for each size.
Buss's theory S₂¹ corresponds roughly to Polynomial Calculus and to the Frege-level systems; weaker theories correspond to weaker proof systems. This correspondence gives a two-way street: lower bounds in proof complexity translate into independence results in bounded arithmetic, and constructions in arithmetic suggest new proof systems. It also connects proof complexity to feasible interpolation — a technique, developed by Krajíček and Pudlák, that extracts an efficient algorithm from a short proof of a certain form, and whose failure for a proof system yields lower bounds.
Simulation, Optimality, and the Hierarchy of Systems
As the zoo of proof systems grew, a central organizing question emerged: when can one system simulate another? System A polynomially simulates system B if every B-proof can be converted into an A-proof of at most polynomial length1. Cook and Reckhow's framework predicted a hierarchy, and researchers mapped it: resolution is simulated by Cutting Planes and by Frege systems; bounded-depth Frege sits below full Frege; algebraic systems interleave with logical ones in complex ways.
The optimality question — whether there is a single strongest proof system that simulates all others — is open and tied to deep questions about self-reference and diagonalization. What is known is a rich partial order, with separation results (proving A does not simulate B) often harder than lower bounds themselves.
Randomized and Probabilistically Checkable Proofs
In the 1990s, the field widened beyond deterministic proofs. Probabilistically checkable proofs (PCPs) — developed by Arora, Safra, and others — showed that every NP statement has a proof that can be verified by reading only a constant number of randomly chosen bits. This theorem, a landmark of complexity theory, redefined what a "proof" could be and connected proof complexity to hardness of approximation. Randomized proof systems, in which the verifier may toss coins, and interactive proofs, where the prover and verifier exchange messages, became part of the broader landscape4. Within proof complexity proper, these ideas informed the study of proof systems with randomness and the limits of efficient verification.
The Present: SAT Solvers, Lower Bounds, and Open Questions
Today proof complexity is both a theoretical and a practical field. On the practical side, the explosion of SAT solving — driven by clause-learning solvers whose behaviour is explained by resolution and its extensions — has made proof complexity essential to understanding why some industrial instances are easy and others hard1. On the theoretical side, the central open problems remain: prove a super-polynomial lower bound for Frege systems (which would separate NP from coNP), determine whether bounded arithmetic theories are finitely axiomatizable, and resolve the optimality question for proof systems.
The main approaches in use descend directly from the history above: resolution and its extensions for solver analysis; algebraic systems for optimization and algebra; bounded arithmetic for logical foundations; and the simulation hierarchy as the organizing map. What unites them is the founding insight of Cook and Reckhow: that a proof is a computational object, and that the question of how hard it is to prove something is a question about the limits of efficient computation itself1.
References
- Proof complexity (introduction, Complexity, Proof systems, Main results, Lower bounds, SAT solvers, Definitions), Wikipedia
- Frege system, Wikipedia
- Bounded arithmetic, Wikipedia
- Interactive proof system, Wikipedia
The frameworks of Proof Complexity
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1935-Present
Sequent Calculus and Cut Elimination
How can proofs be manipulated so that cuts can be removed?
- 1979-Present
- 1979-Present
Propositional proof system
What makes a proof system reasonable and efficient to check?
- 1979-Present
Simulation and Optimality Hierarchy
When can one proof system simulate another?
- 1985-Present
Bounded Arithmetic and Propositional Translations
Which arithmetic theories match which propositional proof systems?
- 1985-Present
- 1990-Present
Algebraic Proof Systems
How hard is it to refute polynomial equations algebraically?
- 1990-Present
Feasible Interpolation
When does a short proof yield an efficient algorithm?
- 1990-Present
Probabilistically Checkable and Interactive Proofs
How few bits must a verifier read to check a proof?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Feasible Interpolation grew out of Bounded Arithmetic and Propositional Translations
Feasible interpolation grew out of the bounded-arithmetic correspondence: a short propositional proof translates into a proof in a bounded theory, from which an algorithm is extracted. Krajíček and Pudlák developed the technique within the propositional-translation programme.
Carried by Jan Krajíček; Pavel Pudlák.
Bounded Arithmetic and Propositional Translations grew out of Frege system
Buss's bounded arithmetic was calibrated so that its strongest theories correspond to Frege systems, with the arithmetic proof translating into a Frege proof family. Frege systems supplied the upper rung of the correspondence.
Carried by Samuel Buss.
Beyond the field
Where Proof Complexity's ideas came from in other fields, and what they led to there: the strongest 12 of 13 links.
Sequent Calculus and Cut Elimination grew out of Proof Theory in Mathematical Logic
Hilbert's proof theory program supplied the questions and aims (consistency, finitary methods) that Gentzen's sequent calculus and cut elimination were devised to serve.
Carried by David Hilbert; Gerhard Gentzen.
Algebraic Proof Systems influenced by Algebraic Complexity Theory in Complexity Theory
Algebraic proof systems such as the Nullstellensatz and polynomial calculus systems were built by importing the language and techniques of algebraic complexity theory, notably arithmetic circuits and polynomial identity testing, into propositional proof complexity.
Feasible Interpolation grew out of Proof Complexity in Theory Of Computation
The complexity-theoretic formulation of proof complexity, with its emphasis on circuit lower bounds, is what feasible interpolation connects to proof length. The method was devised to transfer boolean-circuit lower bounds to propositional proof systems.
Carried by Jan Krajíček; Pavel Pudlák.
Feasible Interpolation grew out of Proof complexity in Proof Theory
Feasible interpolation was developed within proof complexity: Krajíček's method extracts a circuit from a proof of an interpolant, turning lower bounds on circuits into lower bounds on proof size. The proof-theoretic framework supplied the interpolation theorem and the proof systems to which the method was applied.
Carried by Jan Krajíček.
Probabilistically Checkable and Interactive Proofs influenced by Randomized and Interactive Computation in Theory Of Computation
The theory of randomised and interactive computation provided the interactive-proof model and the notion of a verifier that the PCP theorem refines. The framework's central objects are defined within this setting.
Carried by László Babai; Shafi Goldwasser; Silvio Micali.
Probabilistically Checkable and Interactive Proofs influenced by Probabilistic complexity theory in Randomized Algorithms
Probabilistic complexity theory supplied the classes (BPP, IP, PSPACE) and the randomised-verifier model on which interactive proofs and the PCP theorem were built. The definitions of interactive proof and PCP are stated in its terms.
Sequent Calculus and Cut Elimination influenced by Incompleteness and Limitative Metamathematics in Mathematical Logic
Gödel's incompleteness results set the limits that Gentzen's consistency proof by cut elimination (using transfinite induction) was designed to respect and circumvent.
Carried by Kurt Gödel; Gerhard Gentzen.
Sequent Calculus and Cut Elimination influenced by Natural deduction in Proof Theory
Gentzen's natural deduction was the immediate companion system; his sequent calculus was formulated alongside it and cut elimination corresponds to normalization of natural deductions.
Carried by Gerhard Gentzen.
Frege system influenced by Fregean predicate logic in Logic
The Frege system of proof complexity is a propositional proof system modeled on Frege's Begriffsschrift axiomatization of logic, adapted to propositional formulas with axiom schemas and modus ponens.
Carried by Stephen Cook; Robert Reckhow.
Simulation and Optimality Hierarchy influenced by Structural Complexity and the Polynomial Hierarchy in Complexity Theory
The simulation and optimality hierarchy for proof systems was modeled on structural complexity theory's polynomial hierarchy and its notions of simulation between complexity classes.
Carried by Stephen Cook; Robert Reckhow.
Bounded Arithmetic and Propositional Translations influenced by Proof Theory in Mathematical Logic
Bounded arithmetic grows out of proof theory's study of arithmetic theories and their proof-theoretic strength, restricting induction to bounded formulas.
Carried by Samuel Buss.
Resolution influenced by Automated Theorem Proving in Computational Logic
Resolution was introduced by Robinson as a machine-oriented proof rule for automated theorem proving, from which its use as a proof system in complexity was later taken.
Carried by John Alan Robinson.

Proof Complexity is a planet in Nousfarer
Its city has a tower for each of these 9 frameworks. Land, walk in, and climb one concept at a time.
Land on Proof ComplexityRelated fields
Fields its ideas are linked to
- Mathematical Logic 3 links
- Proof Theory 2 links
- Complexity Theory 2 links
- Computational Logic 2 links
- Theory Of Computation 2 links
- Randomized Algorithms 1 link
- Logic 1 link
More in Theory Of Computation
- Algorithmic Game Theory
- Automata
- Complexity Theory
- Computability
- Computational Learning Theory
- Computational Logic
- Cryptography
- Quantum Computation
- Theory Of Computation
See where Proof Complexity sits on the Map of Human Knowledge