Areas Mathematical logic Topic
Propositional proof complexity
Summary
This topic is a part of mathematical logic. It covers the length of proofs of propositional tautologies in proof systems, the hierarchy of proof systems, and the known lower bounds.
Remarks
Reading order
- Proof complexity: the measures of proofs and the aims of the field.
- Propositional proof system: the definition of Cook and Reckhow, and p-simulation.
- Cook–Reckhow theorem: polynomially bounded systems and the question NP versus coNP.
- Frege system: Hilbert-style systems, and Reckhow's theorem that they are p-equivalent.
- Extended Frege system: abbreviations by new variables.
- Lower bounds for Frege systems: the open problem and its barriers.
- Resolution as a proof system: tree-like, regular and dag-like refutations, and SAT solvers.
- Haken's theorem: the first exponential lower bound for resolution.
- Size-width relation for resolution: lower bounds for size from lower bounds for width.
- Tseitin formulas: parity on graphs, hard for resolution on expanders.
- Pigeonhole formulas: the main hard examples, and the systems that refute them.
- Bounded-depth Frege: lines of constant depth, and Ajtai's lower bound.
- Cutting planes: linear inequalities, and Pudlák's lower bound.
- Algebraic proof systems: Nullstellensatz and polynomial calculus, measured by degree.
- Feasible interpolation: circuits from proofs, and lower bounds from circuit lower bounds.
- Automatizability: finding proofs, and the theorem of Atserias and Müller.
Prerequisites
- The propositional calculus: formulas, tautologies, Hilbert systems and resolution.
- Theory of computation: polynomial time, NP, coNP and Boolean circuits.
- Bounded arithmetic: the theories that correspond to the proof systems, for the remarks on logic.
Everything in this topic
The members of this topic and each page that they need, 483 pages in all.
- Algebraically closed field concept
- Alphabet concept
- Arity concept
- Binomial coefficient definition
- Boolean circuit concept
- Boolean function definition
- Boolean function concept
- Cardinality of a finite set definition
- Cartesian product concept
- Cheeger constant concept
- Circuit complexity concept
- Clique concept
- Complexity class concept
- Construction of the reals from Cauchy sequences concept
- Countable set concept
- Countermodel concept
- DPLL algorithm concept
- Decision tree model concept
- Definition by recursion concept
- Deterministic polynomial time concept
- Directed graph definition
- Effectively decidable set concept
- Element definition
- Equality (mathematics) concept
- Factorial definition
- First-order variable concept
- Formal language concept
- Function concept
- Gomory's fractional cut concept
- Graph definition
- Graph colouring concept
- Ideal concept
- Induction on well-formed formulas concept
- Injective function concept
- Integers object
- Limit point of a set definition
- Linear programming concept
- Local maximum definition
- Mathematical statement definition
- Matrix concept
- NP concept
- NP-completeness concept
- Natural numbers object
- Nondeterministic Turing machine concept
- Ordered field definition
- P concept
- Peano axioms concept
- Polynomial ring concept
- Polynomial-time reduction concept
- Polynomials in several variables concept
- Probabilistic method concept
- Proposition concept
- Propositional letter concept
- Radical of an ideal concept
- Random experiment concept
- Rational numbers object
- Real numbers object
- SAT and SMT solving topic
- Semialgebraic set concept
- Sequence definition
- Set concept
- Set bounded above definition
- Strictly monotone function definition
- String concept
- Sum-of-squares optimization concept
- Time complexity concept
- Tuple concept
- co-NP concept
- Proof of Pascal's rule from the recursive definition proof
- Razborov's monotone circuit lower bound statement
- Boolean circuit definition
- Signature concept
- AC0 definition
- Set definition
- Logical connective definition
- Neighbourhood definition
- Binary operation concept
- Hilbert's Nullstellensatz statement
- Ring of integers statement
- Limit of a function definition
- Local minimum definition
- Integer programming definition
- Connectives in mathematical language concept
- NP definition
- Archimedean ordered field definition
- Successor function definition
- Conjunction definition
- Disjunction definition
- Material implication definition
- Principle of bivalence concept
- The reals form a field statement
- Predicate concept
- Predicate definition
- Real sequence definition
- Subsequence definition
- Infimum definition
- Supremum definition
- Pascal's rule statement
- Empty set object
- Ordered pair definition
- Degree of a vertex definition
- Associativity concept
- Identity element concept
- Continuity at a point definition
- Derivative definition
- One-sided limit definition
- Intersection definition
- Union definition
- Structure concept
- Bounded sequence definition
- Cauchy sequence definition
- Geometric sequence definition
- Limit of a sequence definition
- Monotone sequence definition
- Sequence tending to infinity definition
- Series definition
- Addition of natural numbers definition
- Conditional statements concept
- Sample space definition
- Biconditional definition
- Proof of the Archimedean property in an Archimedean ordered field proof
- The successor function is injective statement
- Zero is not a successor statement
- The rationals form a field statement
- Term concept
- Negation concept
- Negation definition
- Positivstellensatz statement
- Completeness axiom statement
- Cartesian product definition
- Regular graph definition
- Disjoint sets definition
- Continuous function definition
- Inverse element concept
- Differentiable function definition
- One-sided derivative definition
- Proof of the factorial formula for binomial coefficients by induction proof
- Limit superior definition
- Proof of the sum of a finite geometric series proof
- Atomic formula concept
- Convergent sequence definition
- Pointwise convergence definition
- Sequential continuity definition
- The sequence r^n tends to infinity for r > 1 example
- Cauchy product definition
- Partial sum definition
- Power series definition
- Archimedean property statement
- Truth table concept
- Quantifiers in mathematical writing concept
- Order on the natural numbers definition
- Material implication concept
- The rationals form an ordered field statement
- Conjunction concept
- Disjunction concept
- Proof that a composition of continuous functions is continuous proof
- Expander graph definition
- Group concept
- Factorial formula for binomial coefficients statement
- Sum of a finite geometric series statement
- Uniform convergence definition
- Radius of convergence definition
- Convergent series definition
- Order on the reals definition
- Negating mathematical statements concept
- Tautology concept
- Universal quantifier concept
- Biconditional concept
- Universal quantifier definition
- Existential quantifier definition
- Ring definition
- Uniform convergence on a set definition
- Interval definition
- Sum of a series definition
- Series of functions definition
- Absolute convergence definition
- Subset definition
- Uniqueness quantifier definition
- Logical equivalence concept
- Proof of the law of excluded middle by a truth table proof
- co-NP definition
- Existential quantifier concept
- Logical connective concept
- Commutative ring definition
- Binary relation definition
- Proof of the epsilon-delta form of continuity proof
- Universal set definition
- Power set definition
- Proof of the epsilon-delta form of the limit of a function proof
- Well-formed formula concept
- Propositional proof system definition member
- Propositional calculus concept
- Law of excluded middle statement
- Proof of the double negation law by a truth table proof
- Propositional formula definition
- Propositional formula concept
- Antisymmetric relation definition
- Reflexive relation definition
- Transitive relation definition
- Proof of the binomial theorem by induction proof
- Epsilon-delta definition of continuity statement
- Function definition
- Epsilon-delta definition of a limit statement
- Complement definition
- First-order logic concept
- The truth-table proof system example member
- Free and bound variables concept
- Double negation law statement
- Proof of unique readability by counting brackets proof
- Formal system concept
- Preorder definition
- Composition of continuous functions is continuous statement
- Binomial theorem statement
- Codomain definition
- Function composition definition
- Injective function definition
- Image of a set definition
- Indicator function definition
- Preimage of a set definition
- Sigma-algebra definition
- Unique readability theorem statement
- Substitution concept
- Partial order definition
- Surjective function definition
- Proof that a composition of injections is injective proof
- Countable set definition
- Event definition
- Truth valuation concept
- Sequent calculus definition
- Borel sigma-algebra definition
- Total order definition
- Proof that a composition of surjections is surjective proof
- Bijective function definition
- Composition of injections is injective statement
- Conjunctive normal form concept
- Disjunctive normal form concept
- Probability axioms concept
- Logical consequence concept
- Clause concept
- Composition of surjections is surjective statement
- Proof of the rule of sum proof
- Probability measure definition
- Functional completeness concept
- Proof of Craig interpolation for propositional logic proof
- Satisfiability concept
- Rule of inference concept
- Proof that the reals form an ordered field, with the Cauchy sequence construction proof
- Algebraic proof systems definition member
- Rule of sum statement
- Probability distribution definition
- Resolution concept
- Equisatisfiability concept
- Craig interpolation for propositional logic statement
- A Nullstellensatz refutation of three clauses example member
- An identity on the Boolean cube that is not a certificate example member
- Direct proof of propositional compactness for countably many variables proof
- Probability space definition
- Modus ponens concept
- The reals form an ordered field statement
- Boolean satisfiability problem problem
- Proof of the complement principle proof
- Tseitin transformation concept
- Compactness theorem for propositional logic statement
- Random variable definition
- Natural deduction concept
- Hilbert system concept
- Mathematical proof concept
- Absolute value definition
- Checking one satisfying assignment is not a proof system example member
- Hilbert system definition
- Cook–Levin theorem statement
- Proof of the approximation property of the supremum proof
- Cumulative distribution function definition
- Law of a random variable definition
- Complement principle statement
- Discrete random variable definition
- Proof of the soundness and completeness of propositional resolution proof
- Random variable with a density definition
- A derivation of p → p in the Hilbert system L example
- Proof theory concept
- Frege system definition member
- Proof of the triangle inequality for real numbers proof
- Proof that the absolute value is multiplicative proof
- The Hilbert system L is a Frege system example member
- Proof of the Cook–Reckhow theorem proof member
- Proof of the epsilon-N definition of the limit of a sequence proof
- Proof by contradiction concept
- Approximation property of the supremum statement
- Mathematical induction concept
- P versus NP problem problem
- Probability density function definition
- Probability mass function definition
- Proof of the pigeonhole principle proof
- Soundness and completeness of propositional resolution statement
- Expected value definition
- Bounded-depth Frege definition member
- Sequent calculus concept
- Lines and size of a proof of p → p in L example member
- Triangle inequality statement
- Absolute value is multiplicative statement
- Extended Frege system definition member
- Proof of Reckhow's theorem for one set of connectives proof member
- Proof complexity concept member
- Cook–Reckhow theorem statement member
- Epsilon-N definition of the limit of a sequence statement
- Proof of the commutativity of addition by induction proof
- Proof of strong induction from ordinary induction proof
- Proof that the reals are Archimedean from the completeness axiom proof
- Law of the unconscious statistician statement
- Linearity of expectation statement
- Resolution as a proof system definition member
- Cut rule definition
- Extension variables for the carries of binary addition example member
- Proof that differentiable functions are continuous proof
- Substitution instances of a fixed proof have bounded depth example member
- Reckhow's theorem on Frege systems statement member
- A self-referential definition p ↔ ¬p is not an extension axiom example member
- Lower bounds for Frege systems problem member
- Proof of the term test proof
- Proof of the squeeze theorem for sequences proof
- Proof of the limit of a sum of sequences proof
- Proof that Cauchy sequences are bounded proof
- Proof that convergent sequences are bounded proof
- Proof that convergent sequences are Cauchy proof
- Proof that limits preserve non-strict inequalities proof
- Proof of the uniqueness of limits proof
- The sequence 1/n tends to zero example
- Commutativity of addition statement
- Pigeonhole principle statement
- Strong induction statement
- The reals are Archimedean statement
- Proof of the monotone convergence theorem for sequences proof
- Moment definition
- Proof of the restriction lemma for resolution proof member
- The measures of a small resolution refutation example member
- Tseitin formulas example member
- Resolution as a Cook-Reckhow proof system example member
- Proof of Markov's inequality proof
- Resolution is not a Frege system example member
- An extended resolution refutation is not a resolution refutation example member
- Differentiable functions are continuous statement
- A tree-like refutation from a DPLL run example member
- Proof of cut elimination with the mix rule proof
- Cutting planes definition member
- An extension step in a proof of (a ∧ b) ∨ ¬(a ∧ b) example member
- Pigeonhole formulas example member
- Proof of the probability of the complement proof
- Cauchy sequences are bounded statement
- Convergent sequences are bounded statement
- Convergent sequences are Cauchy statement
- Squeeze theorem statement
- Limit of a sum of sequences statement
- Proof of the ratio formula for the radius of convergence proof
- Limits preserve non-strict inequalities statement
- Uniqueness of limits statement
- Monotone convergence theorem for sequences statement
- Proof of the well-ordering principle from strong induction proof
- Proof that there is a natural number n with 1/n below any positive epsilon proof
- Moment-generating function definition
- Restriction lemma for resolution statement member
- Feasible interpolation concept member
- Cut-elimination theorem statement
- Probability of the complement statement
- Proof structure of Buss's theorem by counting formulas proof member
- A cutting-planes refutation of the four clauses on two variables example member
- A polynomial calculus refutation for two pigeons and one hole example member
- Rounding without divisibility is unsound example member
- Proof of the limit of a product of sequences proof
- Term test statement
- Proof that a series of nonnegative terms converges iff its partial sums are bounded proof
- The sequence r^n tends to zero for |r| < 1 example
- Proof structure of Ajtai's theorem by the matching switching lemma proof member
- A Chvátal-Gomory cut for three pairwise exclusions example member
- Proof that a decreasing sequence bounded below converges proof
- Well-ordering principle statement
- There is a natural number n with 1/n below any positive epsilon statement
- Proof of the size-width relation for resolution proof member
- Proof of feasible interpolation for resolution proof member
- Resolution as the sequent calculus with atomic cuts example member
- Proof of the monotonicity of probability proof
- Proof structure of Pudlák's lower bound by monotone interpolation proof member
- Geometric series example
- Buss's theorem on Frege proofs of the pigeonhole principle statement member
- Ajtai's theorem on bounded-depth proofs of the pigeonhole principle statement member
- Proof that continuity is equivalent to sequential continuity proof
- Proof of the sequential characterization of limits proof
- Cutting-planes refutation of the pigeonhole formulas by counting proof member
- Limit of a product of sequences statement
- A series of nonnegative terms converges iff its partial sums are bounded statement
- Proof of Haken's theorem by random restrictions proof member
- Decreasing sequence bounded below converges statement
- Proof that every sequence has a monotone subsequence, by peaks proof
- Size-width relation for resolution statement member
- Feasible interpolation for resolution statement member
- Monotonicity of probability statement
- Buss's Frege proofs of the pigeonhole principle are not of bounded depth example member
- Pudlák's lower bound for cutting planes statement member
- Continuity is equivalent to sequential continuity statement
- Proof of the root test proof
- Polynomial cutting-planes refutations of the pigeonhole formulas statement member
- Proof of the ratio test proof
- Sequential characterization of limits statement
- Haken's theorem statement member
- Proof that the Cauchy product of absolutely convergent series converges absolutely to the product proof
- Proof of the Cauchy–Hadamard theorem proof
- Proof of the comparison test proof
- Proof that exponentials dominate powers in sequences, by the ratio of consecutive terms proof
- Every sequence has a monotone subsequence statement
- An interpolant from a refutation of seven clauses example member
- Interpolation by elimination of the private variables example member
- Markov's inequality statement
- Width proof of Urquhart's theorem proof member
- Monotone interpolation and the clique-colouring formulas example member
- Proof of the chain rule with an auxiliary difference quotient proof
- Cauchy product of absolutely convergent series statement
- Proof of the product rule proof
- Comparison test statement
- Proof of the linearity of differentiation proof
- Exponentials dominate powers in sequences statement
- Automatizability concept member
- Proof of the Bolzano–Weierstrass theorem by a monotone subsequence proof
- Urquhart's theorem on Tseitin formulas statement member
- Bounded-width search for resolution refutations example member
- Chain rule statement
- Root test statement
- Ratio test statement
- Product rule statement
- The truth-table system is automatizable example member
- DPLL does not automate general resolution example member
- Linearity of differentiation statement
- Bolzano–Weierstrass theorem statement
- Proof of the power rule by induction proof
- Cauchy–Hadamard theorem statement
- Proof of the constant multiple rule proof
- Ratio formula for the radius of convergence statement
- Proof of the boundedness theorem by Bolzano–Weierstrass proof
- Proof of the Cauchy criterion for sequences by the Bolzano–Weierstrass theorem proof
- Power rule statement
- Constant multiple rule statement
- Boundedness theorem statement
- Cauchy criterion for sequences statement
- Proof of the formula for the derivative of a polynomial proof
- Uniformly Cauchy sequence of functions definition
- Proof of the Cauchy criterion for series proof
- Proof of Fermat's theorem on stationary points proof
- Proof of the extreme value theorem by the Bolzano–Weierstrass theorem proof
- Derivative of a polynomial statement
- Extreme value theorem statement
- Cauchy criterion for series statement
- Fermat's theorem on stationary points statement
- Proof that absolutely convergent series converge proof
- Proof of Rolle's theorem proof
- Rolle's theorem statement
- Absolutely convergent series converge statement
- Proof of the mean value theorem from Rolle's theorem proof
- Proof of the Weierstrass M-test proof
- Mean value theorem statement
- Weierstrass M-test statement
- Proof that uniform convergence of derivatives allows term-by-term differentiation proof
- Proof that power series converge uniformly on smaller intervals inside the radius of convergence proof
- Proof that a function with positive derivative is strictly increasing proof
- Uniform convergence of derivatives allows term-by-term differentiation statement
- Power series converge uniformly on smaller discs inside the radius of convergence statement
- A function with positive derivative is strictly increasing statement
- Proof of term-by-term differentiation proof
- Proof that the exponential series has infinite radius of convergence proof
- Term-by-term differentiation statement
- The exponential series has infinite radius of convergence statement
- Exponential function definition
- Proof that power series are differentiable inside the radius of convergence proof
- Power series are differentiable inside the radius of convergence statement
- Proof of the exponential of a sum by the Cauchy product proof
- Exponential of a sum statement
- Proof that the exponential function is its own derivative, by term-by-term differentiation proof
- Proof that the exponential function is positive proof
- The exponential function is its own derivative statement
- The exponential function is positive statement
- Proof that the exponential function is strictly increasing proof
- The exponential function is strictly increasing statement
- Proof of the Chernoff bound proof
- Chernoff bound statement
- Proof of the Atserias-Müller theorem proof member
- Atserias-Müller theorem statement member
About this page
| Tag | CBAF7J051K |
|---|---|
| URI | m2://CBAF7J051K |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03F20 |
| Part of | Mathematical logic |
| Changed | 18 November 2026, first written 17 November 2026 |
Markdown · JSON · Edit on GitHub
What this page needs for W1
- a same_as or a source (0 of 1)
- an inventory row: the row of the inventory that the node accounts for (0 of 1)
- a source with a locator (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
History
Each change to this page, from its provenance log. A change by an agent names its run.
| Date | Change | Field | By |
|---|---|---|---|
| 2026-11-17 | add | the whole node | tamnd |
| 2026-11-18 | add | the section Remarks | tamnd |
What links here
Nodes in this topic
- Cutting-planes refutation of the pigeonhole formulas by counting
- Proof complexity
- Proof of the Cook–Reckhow theorem
- Proof structure of Ajtai's theorem by the matching switching lemma
- Rounding without divisibility is unsound
- Proof of Reckhow's theorem for one set of connectives
- Propositional proof system
- Polynomial cutting-planes refutations of the pigeonhole formulas
- Bounded-depth Frege
- Haken's theorem
- Feasible interpolation
- Pudlák's lower bound for cutting planes
- Extended Frege system
- Proof of feasible interpolation for resolution
- The truth-table proof system
- Resolution as a proof system
- A Chvátal-Gomory cut for three pairwise exclusions
- Checking one satisfying assignment is not a proof system
- Lines and size of a proof of p → p in L
- Interpolation by elimination of the private variables
- DPLL does not automate general resolution
- Restriction lemma for resolution
- A tree-like refutation from a DPLL run
- Proof of Haken's theorem by random restrictions
- Bounded-width search for resolution refutations
- Proof of the size-width relation for resolution
- An extension step in a proof of (a ∧ b) ∨ ¬(a ∧ b)
- Lower bounds for Frege systems
- The Hilbert system L is a Frege system
- Resolution as the sequent calculus with atomic cuts
- A self-referential definition p ↔ ¬p is not an extension axiom
- An extended resolution refutation is not a resolution refutation
- Monotone interpolation and the clique-colouring formulas
- The truth-table system is automatizable
- A Nullstellensatz refutation of three clauses
- Size-width relation for resolution
- Urquhart's theorem on Tseitin formulas
- Width proof of Urquhart's theorem
- Frege system
- Tseitin formulas
- Proof of the Atserias-Müller theorem
- An interpolant from a refutation of seven clauses
- Cutting planes
- The measures of a small resolution refutation
- Extension variables for the carries of binary addition
- Substitution instances of a fixed proof have bounded depth
- Proof structure of Buss's theorem by counting formulas
- An identity on the Boolean cube that is not a certificate
- Buss's Frege proofs of the pigeonhole principle are not of bounded depth
- Ajtai's theorem on bounded-depth proofs of the pigeonhole principle
- A cutting-planes refutation of the four clauses on two variables
- Proof structure of Pudlák's lower bound by monotone interpolation
- Pigeonhole formulas
- A polynomial calculus refutation for two pigeons and one hole
- Resolution as a Cook-Reckhow proof system
- Buss's theorem on Frege proofs of the pigeonhole principle
- Atserias-Müller theorem
- Automatizability
- Reckhow's theorem on Frege systems
- Feasible interpolation for resolution
- Cook–Reckhow theorem
- Proof of the restriction lemma for resolution
- Resolution is not a Frege system
- Algebraic proof systems