On parallel hierarchies and \(R_k^i\)

DOI10.1016/S0168-0072(97)00035-3zbMath0892.03015MaRDI QIDQ1377627

Stephen Bloch

Publication date: 15 July 1998

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

witnessing theoremconservativityparallel complexity classesbounded arithmetic hierarchyparallel hierarchies

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Hierarchies of computability and definability (03D55)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Functional interpretations of feasibly constructive arithmetic
• Relativized circuit complexity
• On uniform circuit complexity
• On truth-table reducibility to SAT
• Bounded arithmetic and the polynomial hierarchy
• Bounded arithmetic for NC, ALogTIME, L and NL
• Fragments of Bounded Arithmetic and Bounded Query Classes
• Bounded Query Classes
• RelativizedNC
• Alternation
• Provably total functions of intuitionistic bounded arithmetic
• Satisfiability Is Quasilinear Complete in NQL
• Monadic Elementary Formal Systems
• Existence and feasibility in arithmetic
• Notes on polynomially bounded arithmetic