A decisive characterization of BPP
DOI10.1016/S0019-9958(86)80044-4zbMATH Open0616.68049OpenAlexW1967159037WikidataQ60060630 ScholiaQ60060630MaRDI QIDQ4725751FDOQ4725751
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80044-4
Recommendations
random oracleTuring machinesprobabilistic algorithmsprobabilistic classesrandom quantifiercomplexity class BPPpolynomial-time predicate
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Complexity of computation (including implicit computational complexity) (03D15) Algorithms in computer science (68W99) Turing machines and related notions (03D10)
Cited In (26)
- Mathematical Foundations of Computer Science 2003
- Towards logical foundations for probabilistic computation
- Probabilistic quantifiers and games
- Title not available (Why is that?)
- Title not available (Why is that?)
- On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
- On closure properties of bounded two-sided error complexity classes
- Title not available (Why is that?)
- Turing machines with few accepting computations and low sets for PP
- A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
- Title not available (Why is that?)
- Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
- Stathis Zachos at 70!
- ON HIGHER ARTHUR-MERLIN CLASSES
- The complexity of combinatorial problems with succinct input representation
- Finding weak defining hyperplanes of PPS of the BCC model
- Nondeterministic and randomized Boolean hierarchies in communication complexity
- On bounded-probability operators and C\(_ =\)P
- On counting propositional logic and Wagner's hierarchy
- Curry and Howard meet Borel
- Probabilistic complexity classes and lowness
- Generalized lowness and highness and probabilistic complexity classes
- Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
- A Pseudorandom Oracle Characterization of ${\text{BPP}}$
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
This page was built for publication: A decisive characterization of BPP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4725751)
