A decisive characterization of BPP

DOI10.1016/S0019-9958(86)80044-4zbMath0616.68049OpenAlexW1967159037WikidataQ60060630 ScholiaQ60060630MaRDI QIDQ4725751

Hans Heller, Stathis Zachos

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

zbMATH Keywords

Turing machinesprobabilistic algorithmsrandom oracleprobabilistic classesrandom quantifiercomplexity class BPPpolynomial-time predicate

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Algorithms in computer science (68W99)

Related Items (16)

Stathis Zachos at 70! ⋮ A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes ⋮ The complexity of combinatorial problems with succinct input representation ⋮ On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ Probabilistic quantifiers and games ⋮ On closure properties of bounded two-sided error complexity classes ⋮ On counting propositional logic and Wagner's hierarchy ⋮ ON HIGHER ARTHUR-MERLIN CLASSES ⋮ Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy ⋮ Turing machines with few accepting computations and low sets for PP ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Probabilistic complexity classes and lowness ⋮ Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More) ⋮ On bounded-probability operators and C\(_ =\)P ⋮ Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes

This page was built for publication: A decisive characterization of BPP