Generalized lowness and highness and probabilistic complexity classes

DOI10.1007/BF02088291zbMATH Open0679.68087MaRDI QIDQ4729352FDOQ4729352

Authors Andrew Klapper 

Publication date 1989

Published in Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

complexity classespolynomial hierarchybounded probabilistic polynomial-time complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Probabilistic complexity classes and lowness
• A decisive characterization of BPP
• scientific article; zbMATH DE number 1222828
• On boolean lowness and boolean highness
• On Tally Relativizations of $BP$-Complexity Classes

Cites work

• scientific article; zbMATH DE number 4057011 (Why is no real title available?)
• A low and a high hierarchy within NP
• Are there interactive protocols for co-NP languages?
• BPP and the polynomial hierarchy
• Computational Complexity of Probabilistic Turing Machines
• Does co-NP have short interactive proofs ?
• Robustness of probabilistic computational complexity classes under definitional perturbations
• Some observations on the probabilistic algorithms and NP-hard problems
• The knowledge complexity of interactive proof-systems

Cited in

(8)

• On boolean lowness and boolean highness
• PP-lowness and a simple definition of AWPP
• New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
• On bounded-probability operators and C\(_ =\)P
• Probabilistic complexity classes and lowness
• On the Structure of Logspace Probabilistic Complexity Classes
• On closure properties of bounded two-sided error complexity classes
• A decisive characterization of BPP

This page was built for publication: Generalized lowness and highness and probabilistic complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729352)