A decisive characterization of BPP

DOI10.1016/S0019-9958(86)80044-4MaRDI QIDQ4725751zbMATH OpenOpenAlexWikidataFDO

Authors Stathis Zachos, Hans Heller

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

random oracleTuring machinesprobabilistic algorithmsprobabilistic 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) Algorithms in computer science (68W99) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 3880118
• Symmetric alternation captures BPP
• Generalized lowness and highness and probabilistic complexity classes
• A Pseudorandom Oracle Characterization of ${\text{BPP}}$
• scientific article; zbMATH DE number 3943795

Cited in

(28)

• Mathematical Foundations of Computer Science 2003
• Probabilistic quantifiers and games
• Towards logical foundations for probabilistic computation
• scientific article; zbMATH DE number 1839453 (Why is no real title available?)
• scientific article; zbMATH DE number 3943795 (Why is no real title available?)
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• A higher-order characterization of probabilistic polynomial time
• On closure properties of bounded two-sided error complexity classes
• scientific article; zbMATH DE number 2011858 (Why is no real title available?)
• 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
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• scientific article; zbMATH DE number 3880118 (Why is no real title available?)
• Stathis Zachos at 70!
• The complexity of combinatorial problems with succinct input representation
• ON HIGHER ARTHUR-MERLIN CLASSES
• 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
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• On counting propositional logic and Wagner's hierarchy
• Curry and Howard meet Borel
• Probabilistic complexity classes and lowness
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• Generalized lowness and highness 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)