Math 2.0

Areas Mathematical logic Topic

Bounded arithmetic

Summary

This topic is a part of mathematical logic. It covers weak fragments of arithmetic whose provably total functions form complexity classes, their witnessing theorems, and their links to open problems of complexity theory.

Remarks

Reading order

  1. Bounded arithmetic: theories of arithmetic with bounded induction, whose provable functions are complexity classes.
  2. IΔ0 and the linear-time hierarchy: the Δ0\Delta_0-definable sets are the sets in the linear-time hierarchy.
  3. Parikh's theorem: if 𝖨Δ0\mathsf{I}\Delta_0 proves ∀x ∃y φ(x,y)\forall x \, \exists y \, \varphi(x, y) with φ\varphi bounded, then a witness yy exists below a polynomial in xx, provably in 𝖨Δ0\mathsf{I}\Delta_0.
  4. Cook's theory PV: an equational theory with a symbol for every polynomial-time function.
  5. Buss's witnessing theorem: the Σ1b\Sigma^b_1-definable functions of S21S^1_2 are the polynomial-time functions.
  6. Krajíček-Pudlák-Takeuti theorem: a collapse of the theories gives a collapse of the polynomial hierarchy.
  7. Paris-Wilkie translation: from bounded formulas to families of constant-depth propositional formulas.
  8. Pigeonhole principles in bounded arithmetic: which weak theories prove which forms of the pigeonhole principle, with open cases.
  9. Separating the hierarchy of bounded arithmetic: the open problem whether the theories S2iS^i_2 and T2iT^i_2 differ.
  10. Approximate counting in bounded arithmetic: Jeřábek's theory of approximate sizes from the dual weak pigeonhole principle.

Prerequisites

  1. Formal arithmetic and its fragments: Robinson arithmetic, Peano arithmetic and its fragments by induction.
  2. Structural proof theory: the sequent calculus and cut elimination, used in the witnessing proofs.
  3. Natural independence results and fast-growing functions: provably total functions of stronger theories, for comparison.
  4. P and NP: the complexity classes that the theories capture.
  5. Polynomial hierarchy: the classes Σip\Sigma^p_i that match the formulas Σib\Sigma^b_i.

Everything in this topic

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

Show the path as a graph
Bounded arithmetic, concept, no evidence levelBounded arithmeticconceptIΔ0 and the linear-time hierarchy, concept, no evidence levelIΔ0 and the linear-ti…conceptProof of Parikh's theorem by cuts in a nonstandard model, proof, no evidence levelProof of Parikh's the…proofCook's theory PV, definition, no evidence levelCook's theory PVdefinitionElementary function arithmetic is not a theory of bounded arithmetic, example, no evidence levelElementary function a…exampleInteger square roots in S^1_2, example, no evidence levelInteger square roots …exampleParis-Wilkie translation, concept, no evidence levelParis-Wilkie translat…conceptThe halting set is not Δ0-definable, example, no evidence levelThe halting set is no…exampleThe perfect squares form a Δ0-definable set, example, no evidence levelThe perfect squares f…exampleThe primes form a Δ0-definable set, example, no evidence levelThe primes form a Δ0-…exampleParikh's theorem, statement, no evidence levelParikh's theoremstatementApproximate counting in bounded arithmetic, concept, no evidence levelApproximate counting …conceptFeasibly constructive proof, concept, no evidence levelFeasibly constructive…conceptPigeonhole principles in bounded arithmetic, problem, no evidence levelPigeonhole principles…problemThe pigeonhole principle translates to the propositional pigeonhole formulas, example, no evidence levelThe pigeonhole princi…exampleProof of Buss's witnessing theorem by bootstrapping and free-cut elimination, proof, no evidence levelProof of Buss's witne…proofAn unbounded existential formula has no Paris-Wilkie translation, example, no evidence levelAn unbounded existent…exampleThe Paris-Wilkie translation of a bounded totality statement, example, no evidence levelThe Paris-Wilkie tran…exampleThe theory IΔ0 + Ω1, example, no evidence levelThe theory IΔ0 + Ω1exampleApproximate counting does not detect a single element, example, no evidence levelApproximate counting …exampleThe dual weak pigeonhole principle for a polynomial-time function, example, no evidence levelThe dual weak pigeonh…exampleThe copying function is the identity in PV, example, no evidence levelThe copying function …exampleThe successor function in PV, example, no evidence levelThe successor functio…exampleThe totality of exponentiation has no feasibly constructive proof, example, no evidence levelThe totality of expon…exampleBuss's witnessing theorem, statement, no evidence levelBuss's witnessing the…statementA string of high circuit complexity from the dual weak pigeonhole principle, example, no evidence levelA string of high circ…exampleProof of the Krajíček-Pudlák-Takeuti theorem by a Herbrand argument, proof, no evidence levelProof of the Krajíček…proofKrajíček-Pudlák-Takeuti theorem, statement, no evidence levelKrajíček-Pudlák-Takeu…statementSeparating the hierarchy of bounded arithmetic, problem, no evidence levelSeparating the hierar…problem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Bounded arithmetic concept member
  2. IΔ0 and the linear-time hierarchy concept member
  3. Proof of Parikh's theorem by cuts in a nonstandard model proof member
  4. Cook's theory PV definition member
  5. Elementary function arithmetic is not a theory of bounded arithmetic example member
  6. Integer square roots in S^1_2 example member
  7. Paris-Wilkie translation concept member
  8. The halting set is not Δ0-definable example member
  9. The perfect squares form a Δ0-definable set example member
  10. The primes form a Δ0-definable set example member
  11. Parikh's theorem statement member
  12. Approximate counting in bounded arithmetic concept member
  13. Feasibly constructive proof concept member
  14. Pigeonhole principles in bounded arithmetic problem member
  15. The pigeonhole principle translates to the propositional pigeonhole formulas example member
  16. Proof of Buss's witnessing theorem by bootstrapping and free-cut elimination proof member
  17. An unbounded existential formula has no Paris-Wilkie translation example member
  18. The Paris-Wilkie translation of a bounded totality statement example member
  19. The theory IΔ0 + Ω1 example member
  20. Approximate counting does not detect a single element example member
  21. The dual weak pigeonhole principle for a polynomial-time function example member
  22. The copying function is the identity in PV example member
  23. The successor function in PV example member
  24. The totality of exponentiation has no feasibly constructive proof example member
  25. Buss's witnessing theorem statement member
  26. A string of high circuit complexity from the dual weak pigeonhole principle example member
  27. Proof of the Krajíček-Pudlák-Takeuti theorem by a Herbrand argument proof member
  28. Krajíček-Pudlák-Takeuti theorem statement member
  29. Separating the hierarchy of bounded arithmetic problem member
About this page
TagRA380RWEC0
URIm2://RA380RWEC0
Kindtopic
WritingW0 stub
MSC03F30, 03F20
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-17addthe section Remarkstamnd

What links here

Nodes in this topic