Fragments of Bounded Arithmetic and Bounded Query Classes

DOI10.2307/2154418zbMath0787.03047OpenAlexW4242801681WikidataQ106785033 ScholiaQ106785033MaRDI QIDQ3137488

Jan Krajíček

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

zbMATH Keywords

proof theoryoraclebounded query classfragments of bounded arithmeticboolean complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Cut-elimination and normal-form theorems (03F05) First-order arithmetic and fragments (03F30) Metamathematics of constructive systems (03F50)

Related Items (10)

Relating the bounded arithmetic and polynomial time hierarchies ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ On parallel hierarchies and \(R_k^i\) ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ On parallel hierarchies and R ki ⋮ Some consequences of cryptographical conjectures for S 2 1 and EF ⋮ On the computational complexity of cut-reduction ⋮ Bounded theories for polyspace computability ⋮ A Characterisation of Definable NP Search Problems in Peano Arithmetic ⋮ Induction rules in bounded arithmetic

This page was built for publication: Fragments of Bounded Arithmetic and Bounded Query Classes