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

complexity class BPPpolynomial-time predicateprobabilistic algorithmsprobabilistic classesrandom oraclerandom quantifierTuring machines

Mathematics Subject Classification ID

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

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

(32)

• The complexity of combinatorial problems with succinct input representation
• Probabilistic quantifiers and games
• Turing machines with few accepting computations and low sets for PP
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Probabilistic complexity classes and lowness
• Symmetric alternation captures BPP
• On bounded-probability operators and C\(_ =\)P
• The zero-one law holds for BPP
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
• A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
• Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
• A Pseudorandom Oracle Characterization of ${\text{BPP}}$
• A higher-order characterization of probabilistic polynomial time
• scientific article; zbMATH DE number 3880118 (Why is no real title available?)
• scientific article; zbMATH DE number 3943795 (Why is no real title available?)
• Threshold Computation and Cryptographic Security
• scientific article; zbMATH DE number 1156868 (Why is no real title available?)
• scientific article; zbMATH DE number 2011858 (Why is no real title available?)
• Generalized lowness and highness and probabilistic complexity classes
• scientific article; zbMATH DE number 1839453 (Why is no real title available?)
• On closure properties of bounded two-sided error complexity classes
• Stathis Zachos at 70!
• Mathematical Foundations of Computer Science 2003
• ON HIGHER ARTHUR-MERLIN CLASSES
• On counting propositional logic and Wagner's hierarchy
• Finding weak defining hyperplanes of PPS of the BCC model
• Towards logical foundations for probabilistic computation
• Curry and Howard meet Borel
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P

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)