Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy

DOI10.1145/77600.77623MaRDI QIDQ3474281zbMATH OpenOpenAlexFDO

Authors Ker-I Ko

Publication date 1990

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/77600.77623

zbMATH Keywords

machine-independent complexitypolynomial-time hierarchyprobabilistic computationrelativization

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Restricted relativizations of probabilistic polynomial time
• scientific article; zbMATH DE number 3871339
• Fundamentals of Computation Theory

Cited in

(10)

• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality
• Relativized collapsing between BPP and PH under stringent oracle access
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
• In Memoriam: Ker-I Ko (1950–2018)
• scientific article; zbMATH DE number 2019635 (Why is no real title available?)
• Black-Box and Data-Driven Computation
• Fundamentals of Computation Theory
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024

This page was built for publication: Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy

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