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

DOI10.1145/77600.77623zbMath0696.68062OpenAlexW2013098072MaRDI QIDQ3474281

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

polynomial-time hierarchyrelativizationmachine-independent complexityprobabilistic computation

Mathematics Subject Classification ID

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

Related Items (4)

A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Black-Box and Data-Driven Computation

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