Bounded arithmetic

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.

The approach was initiated by Rohit Jivanlal Parikh^[1] in 1971, and later developed by Samuel Buss^[2] and a number of other logicians.

References