UP and the low and high hierarchies: a relativized separation

DOI10.1007/3-540-55719-9_73MaRDI QIDQ5204316zbMATH OpenOpenAlexFDO

Authors Ming-Jye Sheu, Timothy J. Long

Publication date 4 December 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55719-9_73

zbMATH Keywords

high hierarchylow hierarchyoracle machinepolynomial hierarchyrandom restriction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• UP and the low and high hierarchies: A relativized separation
• Separating the low and high hierarchies by oracles
• On Circuit-Size Complexity and the Low Hierarchy in NP
• A refinement of the low and high hierarchies
• scientific article; zbMATH DE number 866668

Cites work

• A low and a high hierarchy within NP
• Complete sets and the polynomial-time hierarchy
• Complexity Measures for Public-Key Cryptosystems
• On counting problems and the polynomial-time hierarchy
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• Separating the low and high hierarchies by oracles
• The extended low hierarchy is an infinite hierarchy
• The polynomial-time hierarchy
• Turing machines with few accepting computations and low sets for PP

Cited in

(2)

• Revisiting a result of Ko
• UP and the low and high hierarchies: A relativized separation

This page was built for publication: \(\mathrm{UP}\) and the low and high hierarchies: a relativized separation

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