The bounded arithmetic hierarchy
From MaRDI portal
Publication:4152523
DOI10.1016/S0019-9958(78)90257-7zbMath0374.02019MaRDI QIDQ4152523
Publication date: 1978
Published in: Information and Control (Search for Journal in Brave)
Related Items
Elementary functions and loop programs ⋮ Elementary realizability ⋮ Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\) ⋮ Positive rudimentarity of the graphs of Ackermann and Grzegorczyk ⋮ An arithmetical characterization of NP ⋮ Functions Definable by Arithmetic Circuits ⋮ The role of rudimentary relations in complexity theory ⋮ Bounded arithmetic, proof complexity and two papers of Parikh