On closure properties of bounded two-sided error complexity classes
From MaRDI portal
Publication:4835865
DOI10.1007/BF01303057zbMath0827.68046MaRDI QIDQ4835865
James S. Royer, Kenneth W. Regan
Publication date: 13 December 1995
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items (2)
Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Strong self-reducibility precludes strong immunity
Cites Work
- Unnamed Item
- Unnamed Item
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- BPP and the polynomial hierarchy
- Strong nondeterministic polynomial-time reducibilities
- NP is as easy as detecting unique solutions
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Probabilistic quantifiers and games
- Graph isomorphism is in the low hierarchy
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- A note on structure and looking back applied to the relative complexity of computable functions
- Some observations on the probabilistic algorithms and NP-hard problems
- Reductions on NP and p-selective sets
- Probabilistic complexity classes and lowness
- Hardness vs randomness
- Robustness of probabilistic computational complexity classes under definitional perturbations
- PP is as Hard as the Polynomial-Time Hierarchy
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- A decisive characterization of BPP
- Generalized lowness and highness and probabilistic complexity classes
This page was built for publication: On closure properties of bounded two-sided error complexity classes
