| 词条 | 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. References1. ^Rohit J. Parikh. Existence and Feasibility in Arithmetic, Jour. Symbolic Logic 36 (1971) 494–508. {{mathlogic-stub}}2. ^Samuel R. Buss. Bounded Arithmetic. Bibliopolis, Naples, Italy, 1986. 1 : Formal theories of arithmetic |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。