Bounded arithmetic is a collective name for a family of weak subtheories of Peano arithmetic. Such theories are typically obtained by requiring that quantifiers be bounded in the induction axiom or equivalent postulates (a bounded quantifier is of the form ∀x ≤ t or ∃x ≤ t, where t is a term not containing x). The main purpose is to characterize one or another class of computational complexity in the sense that a function is provably total if and only if it belongs to a given complexity class.
- Rohit J. Parikh. Existence and Feasibility in Arithmetic, Jour. Symbolic Logic 36 (1971) 494–508.
- Samuel R. Buss. Bounded Arithmetic. Bibliopolis, Naples, Italy, 1986.
|This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.|