Relativized Polynomial Time Hierarchies Having Exactly K Levels

DOI10.1137/0218027MaRDI QIDQ4729353zbMATH OpenOpenAlexFDO

Authors Ker-I Ko

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

zbMATH Keywords

oraclepolynomial time hierarchyrelativization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3871339
• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• Separating the low and high hierarchies by oracles
• The polynomial-time hierarchy and sparse oracles
• Relativized polynomial hierarchies extending two levels

Cited in

(31)

• 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.
• The robustness of LWPP and WPP, with an application to graph reconstruction
• A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality
• Separating the low and high hierarchies by oracles
• The polynomial-time hierarchy and sparse oracles
• In Memoriam: Ker-I Ko (1950–2018)
• Relativized polynomial hierarchies extending two levels
• scientific article; zbMATH DE number 3871339 (Why is no real title available?)
• The polynomial hierarchy for some structures over the binary words
• scientific article; zbMATH DE number 4139728 (Why is no real title available?)
• A note on separating the relativized polynomial time hierarchy by immune sets
• Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy
• A time-space hierarchy between polynomial time and polynomial space
• Structural properties for feasibly computable classes of type two
• A Downward Collapse within the Polynomial Hierarchy
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• UP and the low and high hierarchies: A relativized separation
• The robustness of LWPP and WPP, with an application to graph reconstruction
• A downward translation in the polynomial hierarchy
• The extended low hierarchy is an infinite hierarchy
• \(\mathrm{UP}\) and the low and high hierarchies: a relativized separation
• A relationship between difference hierarchies and relativized polynomial hierarchies
• Fundamentals of Computation Theory
• \(NC^ 1\): The automata-theoretic viewpoint
• Kolmogorov complexity and degrees of tally sets
• On the complexity of ranking

This page was built for publication: Relativized Polynomial Time Hierarchies Having Exactly K Levels

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