BPP and the polynomial hierarchy
From MaRDI portal
Publication:1052094
DOI10.1016/0020-0190(83)90044-3zbMath0515.68042OpenAlexW2036095420WikidataQ56658989 ScholiaQ56658989MaRDI QIDQ1052094
Publication date: 1983
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(83)90044-3
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Error probability in coding theory (94B70) Complexity of proofs (03F20)
Related Items (57)
On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) ⋮ A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ The complexity of combinatorial problems with succinct input representation ⋮ The Journey from NP to TFNP Hardness ⋮ A general method to construct oracles realizing given relationships between complexity classes ⋮ More on BPP and the polynomial-time hierarchy ⋮ Some observations on the connection between counting and recursion ⋮ A note on perfect correctness by derandomization ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Probabilistic quantifiers and games ⋮ Graph isomorphism is in the low hierarchy ⋮ Uniform proofs of ACC representations ⋮ Average-case intractability vs. worst-case intractability ⋮ On closure properties of bounded two-sided error complexity classes ⋮ Computational complexity of the landscape. I. ⋮ On the power of parity polynomial time ⋮ Super-Perfect Zero-Knowledge Proofs ⋮ On the power of deterministic reductions to C=P ⋮ Collision-resistance from multi-collision-resistance ⋮ The Complexity of Aggregates over Extractions by Regular Expressions ⋮ Probabilism versus Alternation for Automata ⋮ Statistically sender-private OT from LPN and derandomization ⋮ Classifying the computational complexity of problems ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Randomness buys depth for approximate counting ⋮ Generalized Quantum Arthur--Merlin Games ⋮ If NP has polynomial-size circuits, then MA=AM ⋮ Non-interactive proofs of proximity ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Challenging epistemology: Interactive proofs and zero knowledge ⋮ Approximate counting in bounded arithmetic ⋮ On sparse hard sets for counting classes ⋮ On zero error algorithms having oracle access to one query ⋮ Complexity classes of equivalence problems revisited ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier? ⋮ Error-bounded probabilistic computations between MA and AM ⋮ On the parameterized complexity of approximate counting ⋮ Probabilistic complexity classes and lowness ⋮ Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More) ⋮ Simplified Derandomization of BPP Using a Hitting Set Generator ⋮ Relations between communication complexity classes ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly ⋮ Generalized lowness and highness and probabilistic complexity classes ⋮ Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly ⋮ How much randomness is needed to convert MA protocols to AM protocols? ⋮ Tally NP sets and easy census functions. ⋮ Robust algorithms: a different approach to oracles ⋮ On bounded-probability operators and C\(_ =\)P ⋮ A Note on Perfect Correctness by Derandomization ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes ⋮ Relativized circuit complexity
Cites Work
This page was built for publication: BPP and the polynomial hierarchy
