Math 2.0

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

  1. Proof complexity: the measures of proofs and the aims of the field.
  2. Propositional proof system: the definition of Cook and Reckhow, and p-simulation.
  3. Cook–Reckhow theorem: polynomially bounded systems and the question NP versus coNP.
  4. Frege system: Hilbert-style systems, and Reckhow's theorem that they are p-equivalent.
  5. Extended Frege system: abbreviations by new variables.
  6. Lower bounds for Frege systems: the open problem and its barriers.
  7. Resolution as a proof system: tree-like, regular and dag-like refutations, and SAT solvers.
  8. Haken's theorem: the first exponential lower bound for resolution.
  9. Size-width relation for resolution: lower bounds for size from lower bounds for width.
  10. Tseitin formulas: parity on graphs, hard for resolution on expanders.
  11. Pigeonhole formulas: the main hard examples, and the systems that refute them.
  12. Bounded-depth Frege: lines of constant depth, and Ajtai's lower bound.
  13. Cutting planes: linear inequalities, and Pudlák's lower bound.
  14. Algebraic proof systems: Nullstellensatz and polynomial calculus, measured by degree.
  15. Feasible interpolation: circuits from proofs, and lower bounds from circuit lower bounds.
  16. Automatizability: finding proofs, and the theorem of Atserias and Müller.

Prerequisites

Everything in this topic

The members of this topic and each page that they need, 483 pages in all.

  1. Algebraically closed field concept
  2. Alphabet concept
  3. Arity concept
  4. Binomial coefficient definition
  5. Boolean circuit concept
  6. Boolean function definition
  7. Boolean function concept
  8. Cardinality of a finite set definition
  9. Cartesian product concept
  10. Cheeger constant concept
  11. Circuit complexity concept
  12. Clique concept
  13. Complexity class concept
  14. Construction of the reals from Cauchy sequences concept
  15. Countable set concept
  16. Countermodel concept
  17. DPLL algorithm concept
  18. Decision tree model concept
  19. Definition by recursion concept
  20. Deterministic polynomial time concept
  21. Directed graph definition
  22. Effectively decidable set concept
  23. Element definition
  24. Equality (mathematics) concept
  25. Factorial definition
  26. First-order variable concept
  27. Formal language concept
  28. Function concept
  29. Gomory's fractional cut concept
  30. Graph definition
  31. Graph colouring concept
  32. Ideal concept
  33. Induction on well-formed formulas concept
  34. Injective function concept
  35. Integers object
  36. Limit point of a set definition
  37. Linear programming concept
  38. Local maximum definition
  39. Mathematical statement definition
  40. Matrix concept
  41. NP concept
  42. NP-completeness concept
  43. Natural numbers object
  44. Nondeterministic Turing machine concept
  45. Ordered field definition
  46. P concept
  47. Peano axioms concept
  48. Polynomial ring concept
  49. Polynomial-time reduction concept
  50. Polynomials in several variables concept
  51. Probabilistic method concept
  52. Proposition concept
  53. Propositional letter concept
  54. Radical of an ideal concept
  55. Random experiment concept
  56. Rational numbers object
  57. Real numbers object
  58. SAT and SMT solving topic
  59. Semialgebraic set concept
  60. Sequence definition
  61. Set concept
  62. Set bounded above definition
  63. Strictly monotone function definition
  64. String concept
  65. Sum-of-squares optimization concept
  66. Time complexity concept
  67. Tuple concept
  68. co-NP concept
  69. Proof of Pascal's rule from the recursive definition proof
  70. Razborov's monotone circuit lower bound statement
  71. Boolean circuit definition
  72. Signature concept
  73. AC0 definition
  74. Set definition
  75. Logical connective definition
  76. Neighbourhood definition
  77. Binary operation concept
  78. Hilbert's Nullstellensatz statement
  79. Ring of integers statement
  80. Limit of a function definition
  81. Local minimum definition
  82. Integer programming definition
  83. Connectives in mathematical language concept
  84. NP definition
  85. Archimedean ordered field definition
  86. Successor function definition
  87. Conjunction definition
  88. Disjunction definition
  89. Material implication definition
  90. Principle of bivalence concept
  91. The reals form a field statement
  92. Predicate concept
  93. Predicate definition
  94. Real sequence definition
  95. Subsequence definition
  96. Infimum definition
  97. Supremum definition
  98. Pascal's rule statement
  99. Empty set object
  100. Ordered pair definition
  101. Degree of a vertex definition
  102. Associativity concept
  103. Identity element concept
  104. Continuity at a point definition
  105. Derivative definition
  106. One-sided limit definition
  107. Intersection definition
  108. Union definition
  109. Structure concept
  110. Bounded sequence definition
  111. Cauchy sequence definition
  112. Geometric sequence definition
  113. Limit of a sequence definition
  114. Monotone sequence definition
  115. Sequence tending to infinity definition
  116. Series definition
  117. Addition of natural numbers definition
  118. Conditional statements concept
  119. Sample space definition
  120. Biconditional definition
  121. Proof of the Archimedean property in an Archimedean ordered field proof
  122. The successor function is injective statement
  123. Zero is not a successor statement
  124. The rationals form a field statement
  125. Term concept
  126. Negation concept
  127. Negation definition
  128. Positivstellensatz statement
  129. Completeness axiom statement
  130. Cartesian product definition
  131. Regular graph definition
  132. Disjoint sets definition
  133. Continuous function definition
  134. Inverse element concept
  135. Differentiable function definition
  136. One-sided derivative definition
  137. Proof of the factorial formula for binomial coefficients by induction proof
  138. Limit superior definition
  139. Proof of the sum of a finite geometric series proof
  140. Atomic formula concept
  141. Convergent sequence definition
  142. Pointwise convergence definition
  143. Sequential continuity definition
  144. The sequence r^n tends to infinity for r > 1 example
  145. Cauchy product definition
  146. Partial sum definition
  147. Power series definition
  148. Archimedean property statement
  149. Truth table concept
  150. Quantifiers in mathematical writing concept
  151. Order on the natural numbers definition
  152. Material implication concept
  153. The rationals form an ordered field statement
  154. Conjunction concept
  155. Disjunction concept
  156. Proof that a composition of continuous functions is continuous proof
  157. Expander graph definition
  158. Group concept
  159. Factorial formula for binomial coefficients statement
  160. Sum of a finite geometric series statement
  161. Uniform convergence definition
  162. Radius of convergence definition
  163. Convergent series definition
  164. Order on the reals definition
  165. Negating mathematical statements concept
  166. Tautology concept
  167. Universal quantifier concept
  168. Biconditional concept
  169. Universal quantifier definition
  170. Existential quantifier definition
  171. Ring definition
  172. Uniform convergence on a set definition
  173. Interval definition
  174. Sum of a series definition
  175. Series of functions definition
  176. Absolute convergence definition
  177. Subset definition
  178. Uniqueness quantifier definition
  179. Logical equivalence concept
  180. Proof of the law of excluded middle by a truth table proof
  181. co-NP definition
  182. Existential quantifier concept
  183. Logical connective concept
  184. Commutative ring definition
  185. Binary relation definition
  186. Proof of the epsilon-delta form of continuity proof
  187. Universal set definition
  188. Power set definition
  189. Proof of the epsilon-delta form of the limit of a function proof
  190. Well-formed formula concept
  191. Propositional proof system definition member
  192. Propositional calculus concept
  193. Law of excluded middle statement
  194. Proof of the double negation law by a truth table proof
  195. Propositional formula definition
  196. Propositional formula concept
  197. Antisymmetric relation definition
  198. Reflexive relation definition
  199. Transitive relation definition
  200. Proof of the binomial theorem by induction proof
  201. Epsilon-delta definition of continuity statement
  202. Function definition
  203. Epsilon-delta definition of a limit statement
  204. Complement definition
  205. First-order logic concept
  206. The truth-table proof system example member
  207. Free and bound variables concept
  208. Double negation law statement
  209. Proof of unique readability by counting brackets proof
  210. Formal system concept
  211. Preorder definition
  212. Composition of continuous functions is continuous statement
  213. Binomial theorem statement
  214. Codomain definition
  215. Function composition definition
  216. Injective function definition
  217. Image of a set definition
  218. Indicator function definition
  219. Preimage of a set definition
  220. Sigma-algebra definition
  221. Unique readability theorem statement
  222. Substitution concept
  223. Partial order definition
  224. Surjective function definition
  225. Proof that a composition of injections is injective proof
  226. Countable set definition
  227. Event definition
  228. Truth valuation concept
  229. Sequent calculus definition
  230. Borel sigma-algebra definition
  231. Total order definition
  232. Proof that a composition of surjections is surjective proof
  233. Bijective function definition
  234. Composition of injections is injective statement
  235. Conjunctive normal form concept
  236. Disjunctive normal form concept
  237. Probability axioms concept
  238. Logical consequence concept
  239. Clause concept
  240. Composition of surjections is surjective statement
  241. Proof of the rule of sum proof
  242. Probability measure definition
  243. Functional completeness concept
  244. Proof of Craig interpolation for propositional logic proof
  245. Satisfiability concept
  246. Rule of inference concept
  247. Proof that the reals form an ordered field, with the Cauchy sequence construction proof
  248. Algebraic proof systems definition member
  249. Rule of sum statement
  250. Probability distribution definition
  251. Resolution concept
  252. Equisatisfiability concept
  253. Craig interpolation for propositional logic statement
  254. A Nullstellensatz refutation of three clauses example member
  255. An identity on the Boolean cube that is not a certificate example member
  256. Direct proof of propositional compactness for countably many variables proof
  257. Probability space definition
  258. Modus ponens concept
  259. The reals form an ordered field statement
  260. Boolean satisfiability problem problem
  261. Proof of the complement principle proof
  262. Tseitin transformation concept
  263. Compactness theorem for propositional logic statement
  264. Random variable definition
  265. Natural deduction concept
  266. Hilbert system concept
  267. Mathematical proof concept
  268. Absolute value definition
  269. Checking one satisfying assignment is not a proof system example member
  270. Hilbert system definition
  271. Cook–Levin theorem statement
  272. Proof of the approximation property of the supremum proof
  273. Cumulative distribution function definition
  274. Law of a random variable definition
  275. Complement principle statement
  276. Discrete random variable definition
  277. Proof of the soundness and completeness of propositional resolution proof
  278. Random variable with a density definition
  279. A derivation of p → p in the Hilbert system L example
  280. Proof theory concept
  281. Frege system definition member
  282. Proof of the triangle inequality for real numbers proof
  283. Proof that the absolute value is multiplicative proof
  284. The Hilbert system L is a Frege system example member
  285. Proof of the Cook–Reckhow theorem proof member
  286. Proof of the epsilon-N definition of the limit of a sequence proof
  287. Proof by contradiction concept
  288. Approximation property of the supremum statement
  289. Mathematical induction concept
  290. P versus NP problem problem
  291. Probability density function definition
  292. Probability mass function definition
  293. Proof of the pigeonhole principle proof
  294. Soundness and completeness of propositional resolution statement
  295. Expected value definition
  296. Bounded-depth Frege definition member
  297. Sequent calculus concept
  298. Lines and size of a proof of p → p in L example member
  299. Triangle inequality statement
  300. Absolute value is multiplicative statement
  301. Extended Frege system definition member
  302. Proof of Reckhow's theorem for one set of connectives proof member
  303. Proof complexity concept member
  304. Cook–Reckhow theorem statement member
  305. Epsilon-N definition of the limit of a sequence statement
  306. Proof of the commutativity of addition by induction proof
  307. Proof of strong induction from ordinary induction proof
  308. Proof that the reals are Archimedean from the completeness axiom proof
  309. Law of the unconscious statistician statement
  310. Linearity of expectation statement
  311. Resolution as a proof system definition member
  312. Cut rule definition
  313. Extension variables for the carries of binary addition example member
  314. Proof that differentiable functions are continuous proof
  315. Substitution instances of a fixed proof have bounded depth example member
  316. Reckhow's theorem on Frege systems statement member
  317. A self-referential definition p ↔ ¬p is not an extension axiom example member
  318. Lower bounds for Frege systems problem member
  319. Proof of the term test proof
  320. Proof of the squeeze theorem for sequences proof
  321. Proof of the limit of a sum of sequences proof
  322. Proof that Cauchy sequences are bounded proof
  323. Proof that convergent sequences are bounded proof
  324. Proof that convergent sequences are Cauchy proof
  325. Proof that limits preserve non-strict inequalities proof
  326. Proof of the uniqueness of limits proof
  327. The sequence 1/n tends to zero example
  328. Commutativity of addition statement
  329. Pigeonhole principle statement
  330. Strong induction statement
  331. The reals are Archimedean statement
  332. Proof of the monotone convergence theorem for sequences proof
  333. Moment definition
  334. Proof of the restriction lemma for resolution proof member
  335. The measures of a small resolution refutation example member
  336. Tseitin formulas example member
  337. Resolution as a Cook-Reckhow proof system example member
  338. Proof of Markov's inequality proof
  339. Resolution is not a Frege system example member
  340. An extended resolution refutation is not a resolution refutation example member
  341. Differentiable functions are continuous statement
  342. A tree-like refutation from a DPLL run example member
  343. Proof of cut elimination with the mix rule proof
  344. Cutting planes definition member
  345. An extension step in a proof of (a ∧ b) ∨ ¬(a ∧ b) example member
  346. Pigeonhole formulas example member
  347. Proof of the probability of the complement proof
  348. Cauchy sequences are bounded statement
  349. Convergent sequences are bounded statement
  350. Convergent sequences are Cauchy statement
  351. Squeeze theorem statement
  352. Limit of a sum of sequences statement
  353. Proof of the ratio formula for the radius of convergence proof
  354. Limits preserve non-strict inequalities statement
  355. Uniqueness of limits statement
  356. Monotone convergence theorem for sequences statement
  357. Proof of the well-ordering principle from strong induction proof
  358. Proof that there is a natural number n with 1/n below any positive epsilon proof
  359. Moment-generating function definition
  360. Restriction lemma for resolution statement member
  361. Feasible interpolation concept member
  362. Cut-elimination theorem statement
  363. Probability of the complement statement
  364. Proof structure of Buss's theorem by counting formulas proof member
  365. A cutting-planes refutation of the four clauses on two variables example member
  366. A polynomial calculus refutation for two pigeons and one hole example member
  367. Rounding without divisibility is unsound example member
  368. Proof of the limit of a product of sequences proof
  369. Term test statement
  370. Proof that a series of nonnegative terms converges iff its partial sums are bounded proof
  371. The sequence r^n tends to zero for |r| < 1 example
  372. Proof structure of Ajtai's theorem by the matching switching lemma proof member
  373. A Chvátal-Gomory cut for three pairwise exclusions example member
  374. Proof that a decreasing sequence bounded below converges proof
  375. Well-ordering principle statement
  376. There is a natural number n with 1/n below any positive epsilon statement
  377. Proof of the size-width relation for resolution proof member
  378. Proof of feasible interpolation for resolution proof member
  379. Resolution as the sequent calculus with atomic cuts example member
  380. Proof of the monotonicity of probability proof
  381. Proof structure of Pudlák's lower bound by monotone interpolation proof member
  382. Geometric series example
  383. Buss's theorem on Frege proofs of the pigeonhole principle statement member
  384. Ajtai's theorem on bounded-depth proofs of the pigeonhole principle statement member
  385. Proof that continuity is equivalent to sequential continuity proof
  386. Proof of the sequential characterization of limits proof
  387. Cutting-planes refutation of the pigeonhole formulas by counting proof member
  388. Limit of a product of sequences statement
  389. A series of nonnegative terms converges iff its partial sums are bounded statement
  390. Proof of Haken's theorem by random restrictions proof member
  391. Decreasing sequence bounded below converges statement
  392. Proof that every sequence has a monotone subsequence, by peaks proof
  393. Size-width relation for resolution statement member
  394. Feasible interpolation for resolution statement member
  395. Monotonicity of probability statement
  396. Buss's Frege proofs of the pigeonhole principle are not of bounded depth example member
  397. Pudlák's lower bound for cutting planes statement member
  398. Continuity is equivalent to sequential continuity statement
  399. Proof of the root test proof
  400. Polynomial cutting-planes refutations of the pigeonhole formulas statement member
  401. Proof of the ratio test proof
  402. Sequential characterization of limits statement
  403. Haken's theorem statement member
  404. Proof that the Cauchy product of absolutely convergent series converges absolutely to the product proof
  405. Proof of the Cauchy–Hadamard theorem proof
  406. Proof of the comparison test proof
  407. Proof that exponentials dominate powers in sequences, by the ratio of consecutive terms proof
  408. Every sequence has a monotone subsequence statement
  409. An interpolant from a refutation of seven clauses example member
  410. Interpolation by elimination of the private variables example member
  411. Markov's inequality statement
  412. Width proof of Urquhart's theorem proof member
  413. Monotone interpolation and the clique-colouring formulas example member
  414. Proof of the chain rule with an auxiliary difference quotient proof
  415. Cauchy product of absolutely convergent series statement
  416. Proof of the product rule proof
  417. Comparison test statement
  418. Proof of the linearity of differentiation proof
  419. Exponentials dominate powers in sequences statement
  420. Automatizability concept member
  421. Proof of the Bolzano–Weierstrass theorem by a monotone subsequence proof
  422. Urquhart's theorem on Tseitin formulas statement member
  423. Bounded-width search for resolution refutations example member
  424. Chain rule statement
  425. Root test statement
  426. Ratio test statement
  427. Product rule statement
  428. The truth-table system is automatizable example member
  429. DPLL does not automate general resolution example member
  430. Linearity of differentiation statement
  431. Bolzano–Weierstrass theorem statement
  432. Proof of the power rule by induction proof
  433. Cauchy–Hadamard theorem statement
  434. Proof of the constant multiple rule proof
  435. Ratio formula for the radius of convergence statement
  436. Proof of the boundedness theorem by Bolzano–Weierstrass proof
  437. Proof of the Cauchy criterion for sequences by the Bolzano–Weierstrass theorem proof
  438. Power rule statement
  439. Constant multiple rule statement
  440. Boundedness theorem statement
  441. Cauchy criterion for sequences statement
  442. Proof of the formula for the derivative of a polynomial proof
  443. Uniformly Cauchy sequence of functions definition
  444. Proof of the Cauchy criterion for series proof
  445. Proof of Fermat's theorem on stationary points proof
  446. Proof of the extreme value theorem by the Bolzano–Weierstrass theorem proof
  447. Derivative of a polynomial statement
  448. Extreme value theorem statement
  449. Cauchy criterion for series statement
  450. Fermat's theorem on stationary points statement
  451. Proof that absolutely convergent series converge proof
  452. Proof of Rolle's theorem proof
  453. Rolle's theorem statement
  454. Absolutely convergent series converge statement
  455. Proof of the mean value theorem from Rolle's theorem proof
  456. Proof of the Weierstrass M-test proof
  457. Mean value theorem statement
  458. Weierstrass M-test statement
  459. Proof that uniform convergence of derivatives allows term-by-term differentiation proof
  460. Proof that power series converge uniformly on smaller intervals inside the radius of convergence proof
  461. Proof that a function with positive derivative is strictly increasing proof
  462. Uniform convergence of derivatives allows term-by-term differentiation statement
  463. Power series converge uniformly on smaller discs inside the radius of convergence statement
  464. A function with positive derivative is strictly increasing statement
  465. Proof of term-by-term differentiation proof
  466. Proof that the exponential series has infinite radius of convergence proof
  467. Term-by-term differentiation statement
  468. The exponential series has infinite radius of convergence statement
  469. Exponential function definition
  470. Proof that power series are differentiable inside the radius of convergence proof
  471. Power series are differentiable inside the radius of convergence statement
  472. Proof of the exponential of a sum by the Cauchy product proof
  473. Exponential of a sum statement
  474. Proof that the exponential function is its own derivative, by term-by-term differentiation proof
  475. Proof that the exponential function is positive proof
  476. The exponential function is its own derivative statement
  477. The exponential function is positive statement
  478. Proof that the exponential function is strictly increasing proof
  479. The exponential function is strictly increasing statement
  480. Proof of the Chernoff bound proof
  481. Chernoff bound statement
  482. Proof of the Atserias-Müller theorem proof member
  483. Atserias-Müller theorem statement member
About this page
TagCBAF7J051K
URIm2://CBAF7J051K
Kindtopic
WritingW0 stub
MSC03F20
Part ofMathematical logic
Changed18 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.

The changes to this page, the oldest first
DateChangeFieldBy
2026-11-17addthe whole nodetamnd
2026-11-18addthe section Remarkstamnd

What links here

Nodes in this topic