Fragments of Bounded Arithmetic and Bounded Query Classes
From MaRDI portal
Publication:3137488
DOI10.2307/2154418zbMath0787.03047WikidataQ106785033 ScholiaQ106785033MaRDI QIDQ3137488
Publication date: 23 May 1994
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2154418
03D15: Complexity of computation (including implicit computational complexity)
03F05: Cut-elimination and normal-form theorems
03F30: First-order arithmetic and fragments
03F50: Metamathematics of constructive systems
Related Items
On the computational complexity of cut-reduction, On parallel hierarchies and \(R_k^i\), Some consequences of cryptographical conjectures for \(S_2^1\) and EF, Relating the bounded arithmetic and polynomial time hierarchies, Induction rules in bounded arithmetic, Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\), Bounded theories for polyspace computability, A Characterisation of Definable NP Search Problems in Peano Arithmetic