Relativized Polynomial Time Hierarchies Having Exactly K Levels
From MaRDI portal
Publication:4729353
DOI10.1137/0218027zbMath0679.68088OpenAlexW2000291823MaRDI 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
Related Items (22)
Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ A downward translation in the polynomial hierarchy ⋮ A general method to construct oracles realizing given relationships between complexity classes ⋮ Separating the low and high hierarchies by oracles ⋮ Index sets and presentations of complexity classes ⋮ Structural properties for feasibly computable classes of type two ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ The extended low hierarchy is an infinite hierarchy ⋮ Unnamed Item ⋮ Kolmogorov complexity and degrees of tally sets ⋮ On the complexity of ranking ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ UP and the low and high hierarchies: A relativized separation ⋮ \(NC^ 1\): The automata-theoretic viewpoint ⋮ UP and the low and high hierarchies: A relativized separation ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy ⋮ Relating polynomial time to constant depth ⋮ Time-space tradeoffs for satisfiability ⋮ A Downward Collapse within the Polynomial Hierarchy ⋮ Tally NP sets and easy census functions.
This page was built for publication: Relativized Polynomial Time Hierarchies Having Exactly K Levels
