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

still a working view ended · each leads to its entry below

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

  1. Proof complexity (introduction, Complexity, Proof systems, Main results, Lower bounds, SAT solvers, Definitions), Wikipedia
  2. Frege system, Wikipedia
  3. Bounded arithmetic, Wikipedia
  4. 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.

  1. 1935-Present

    Sequent Calculus and Cut Elimination

    How can proofs be manipulated so that cuts can be removed?

    Fly to its tower in Nousfarer

  2. 1979-Present

    Frege system

    How long are proofs in ordinary logical calculi?

    Fly to its tower in Nousfarer

  3. 1979-Present

    Propositional proof system

    What makes a proof system reasonable and efficient to check?

    Fly to its tower in Nousfarer

  4. 1979-Present

    Simulation and Optimality Hierarchy

    When can one proof system simulate another?

    Fly to its tower in Nousfarer

  5. 1985-Present

    Bounded Arithmetic and Propositional Translations

    Which arithmetic theories match which propositional proof systems?

    Fly to its tower in Nousfarer

  6. 1985-Present

    Resolution

    How long must clause-based refutations be?

    Fly to its tower in Nousfarer

  7. 1990-Present

    Algebraic Proof Systems

    How hard is it to refute polynomial equations algebraically?

    Fly to its tower in Nousfarer

  8. 1990-Present

    Feasible Interpolation

    When does a short proof yield an efficient algorithm?

    Fly to its tower in Nousfarer

  9. 1990-Present

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.

Sequent Calculus and Cut EliminationFrege systemPropositional proof systemSimulation and Optimality HierarchyBounded Arithmetic and Propositional …ResolutionAlgebraic Proof SystemsFeasible InterpolationProbabilistically Checkable and Inter…

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Complexity

Related fields

Fields its ideas are linked to

More in Theory Of Computation

See where Proof Complexity sits on the Map of Human Knowledge