Generalized lowness and highness and probabilistic complexity classes

DOI10.1007/BF02088291zbMath0679.68087MaRDI QIDQ4729352

Andrew Klapper

Publication date: 1989

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

zbMATH Keywords

polynomial hierarchycomplexity classesbounded probabilistic polynomial-time complexity classes

Mathematics Subject Classification ID

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

Related Items

On closure properties of bounded two-sided error complexity classes, Probabilistic complexity classes and lowness

Cites Work

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