Fragments of Bounded Arithmetic and Bounded Query Classes

DOI10.2307/2154418MaRDI QIDQ3137488zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 4059391
• Bounded arithmetic and the polynomial hierarchy
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Witnessing functions in bounded arithmetic and search problems
• Bounded arithmetic and truth definition

Cited in

(15)

• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• Bounded query classes and the difference hierarchy
• Computer Science Logic
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• A Characterisation of Definable NP Search Problems in Peano Arithmetic
• Bounded theories for polyspace computability
• 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
• Relating the bounded arithmetic and polynomial time hierarchies
• On the computational complexity of cut-reduction
• scientific article; zbMATH DE number 440477 (Why is no real title available?)
• scientific article; zbMATH DE number 1420845 (Why is no real title available?)
• Induction rules in bounded arithmetic
• On parallel hierarchies and R_k^i

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3137488)