UP and the low and high hierarchies: A relativized separation

DOI10.1007/3-540-55719-9_73zbMath1425.68129OpenAlexW1580225003MaRDI QIDQ5204316

Timothy J. Long, Ming-Jye Sheu

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

polynomial hierarchyrandom restrictionhigh hierarchylow hierarchyoracle machine

Mathematics Subject Classification ID

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

Cites Work

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

This page was built for publication: UP and the low and high hierarchies: A relativized separation