On parallel hierarchies and R ki

DOI10.1007/3-540-60178-3_79MaRDI QIDQ6064276

Stephen Bloch

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

polynomial hierarchycomplexity classoracle querycircuit familyquantify Boolean formula

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relativized circuit complexity
• On uniform circuit complexity
• Arithmetizing uniform \(NC\)
• Bounded arithmetic and the polynomial hierarchy
• Bounded arithmetic for NC, ALogTIME, L and NL
• A new recursion-theoretic characterization of the polytime functions
• Function-algebraic characterizations of log and polylog parallel time
• Relating the bounded arithmetic and polynomial time hierarchies
• Fragments of Bounded Arithmetic and Bounded Query Classes
• RelativizedNC
• Alternation
• Satisfiability Is Quasilinear Complete in NQL
• Existence and feasibility in arithmetic

This page was built for publication: On parallel hierarchies and R ki