Relativized Polynomial Time Hierarchies Having Exactly K Levels
From MaRDI portal
Publication:4729353
DOI10.1137/0218027zbMath0679.68088MaRDI QIDQ4729353
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218027
68Q25: Analysis of algorithms and problem complexity
Related Items
Immunity and Simplicity for Exact Counting and Other Counting Classes, UP and the low and high hierarchies: A relativized separation, \(NC^ 1\): The automata-theoretic viewpoint, Kolmogorov complexity and degrees of tally sets, On the complexity of ranking, A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy, Relating polynomial time to constant depth, A general method to construct oracles realizing given relationships between complexity classes, Index sets and presentations of complexity classes, Time-space tradeoffs for satisfiability, Tally NP sets and easy census functions., Separating the low and high hierarchies by oracles, A note on separating the relativized polynomial time hierarchy by immune sets, Structural properties for feasibly computable classes of type two, A Downward Collapse within the Polynomial Hierarchy