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
- Bounded arithmetic: theories of arithmetic with bounded induction, whose provable functions are complexity classes.
- IΔ0 and the linear-time hierarchy: the -definable sets are the sets in the linear-time hierarchy.
- Parikh's theorem: if proves with bounded, then a witness exists below a polynomial in , provably in .
- Cook's theory PV: an equational theory with a symbol for every polynomial-time function.
- Buss's witnessing theorem: the -definable functions of are the polynomial-time functions.
- Krajíček-Pudlák-Takeuti theorem: a collapse of the theories gives a collapse of the polynomial hierarchy.
- Paris-Wilkie translation: from bounded formulas to families of constant-depth propositional formulas.
- Pigeonhole principles in bounded arithmetic: which weak theories prove which forms of the pigeonhole principle, with open cases.
- Separating the hierarchy of bounded arithmetic: the open problem whether the theories and differ.
- Approximate counting in bounded arithmetic: Jeřábek's theory of approximate sizes from the dual weak pigeonhole principle.
Prerequisites
- Formal arithmetic and its fragments: Robinson arithmetic, Peano arithmetic and its fragments by induction.
- Structural proof theory: the sequent calculus and cut elimination, used in the witnessing proofs.
- Natural independence results and fast-growing functions: provably total functions of stronger theories, for comparison.
- P and NP: the complexity classes that the theories capture.
- Polynomial hierarchy: the classes that match the formulas .
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
- no evidence level
- Bounded arithmetic concept member
- IΔ0 and the linear-time hierarchy concept member
- Proof of Parikh's theorem by cuts in a nonstandard model proof member
- Cook's theory PV definition member
- Elementary function arithmetic is not a theory of bounded arithmetic example member
- Integer square roots in S^1_2 example member
- Paris-Wilkie translation concept member
- The halting set is not Δ0-definable example member
- The perfect squares form a Δ0-definable set example member
- The primes form a Δ0-definable set example member
- Parikh's theorem statement member
- Approximate counting in bounded arithmetic concept member
- Feasibly constructive proof concept member
- Pigeonhole principles in bounded arithmetic problem member
- The pigeonhole principle translates to the propositional pigeonhole formulas example member
- Proof of Buss's witnessing theorem by bootstrapping and free-cut elimination proof member
- An unbounded existential formula has no Paris-Wilkie translation example member
- The Paris-Wilkie translation of a bounded totality statement example member
- The theory IΔ0 + Ω1 example member
- Approximate counting does not detect a single element example member
- The dual weak pigeonhole principle for a polynomial-time function example member
- The copying function is the identity in PV example member
- The successor function in PV example member
- The totality of exponentiation has no feasibly constructive proof example member
- Buss's witnessing theorem statement member
- A string of high circuit complexity from the dual weak pigeonhole principle example member
- Proof of the Krajíček-Pudlák-Takeuti theorem by a Herbrand argument proof member
- Krajíček-Pudlák-Takeuti theorem statement member
- Separating the hierarchy of bounded arithmetic problem member
About this page
| Tag | RA380RWEC0 |
|---|---|
| URI | m2://RA380RWEC0 |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03F30, 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-17 | add | the section Remarks | tamnd |
What links here
Nodes in this topic
- Integer square roots in S^1_2
- The perfect squares form a Δ0-definable set
- Proof of Parikh's theorem by cuts in a nonstandard model
- The totality of exponentiation has no feasibly constructive proof
- Approximate counting in bounded arithmetic
- The copying function is the identity in PV
- The pigeonhole principle translates to the propositional pigeonhole formulas
- Bounded arithmetic
- The primes form a Δ0-definable set
- A string of high circuit complexity from the dual weak pigeonhole principle
- Cook's theory PV
- An unbounded existential formula has no Paris-Wilkie translation
- IΔ0 and the linear-time hierarchy
- The successor function in PV
- Feasibly constructive proof
- Approximate counting does not detect a single element
- The dual weak pigeonhole principle for a polynomial-time function
- Proof of Buss's witnessing theorem by bootstrapping and free-cut elimination
- Pigeonhole principles in bounded arithmetic
- The halting set is not Δ0-definable
- Separating the hierarchy of bounded arithmetic
- Proof of the Krajíček-Pudlák-Takeuti theorem by a Herbrand argument
- Buss's witnessing theorem
- Elementary function arithmetic is not a theory of bounded arithmetic
- The Paris-Wilkie translation of a bounded totality statement
- The theory IΔ0 + Ω1
- Krajíček-Pudlák-Takeuti theorem
- Parikh's theorem
- Paris-Wilkie translation