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)

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

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)

Cites Work

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

Cited In (8)

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

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)