On closure properties of bounded two-sided error complexity classes

DOI10.1007/BF01303057MaRDI QIDQ4835865zbMATH OpenFDO

Authors James S. Royer, Kenneth W. Regan

Publication date 13 December 1995

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

zbMATH Keywords

complexity class

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Probabilistic complexity classes and lowness
• On Tally Relativizations of $BP$-Complexity Classes
• On bounded-probability operators and C\(_ =\)P
• Probabilistic quantifiers and games
• Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)

Cites work

• scientific article; zbMATH DE number 8788 (Why is no real title available?)
• scientific article; zbMATH DE number 176508 (Why is no real title available?)
• A decisive characterization of BPP
• A note on structure and looking back applied to the relative complexity of computable functions
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• BPP and the polynomial hierarchy
• Generalized lowness and highness and probabilistic complexity classes
• Graph isomorphism is in the low hierarchy
• Hardness vs randomness
• NP is as easy as detecting unique solutions
• PP is as Hard as the Polynomial-Time Hierarchy
• Probabilistic complexity classes and lowness
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Probabilistic quantifiers and games
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Reductions on NP and p-selective sets
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Robustness of probabilistic computational complexity classes under definitional perturbations
• Some observations on the probabilistic algorithms and NP-hard problems
• Strong nondeterministic polynomial-time reducibilities
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

Cited in

(7)

• Mathematical Foundations of Computer Science 2003
• Bounds and constructions for TWOOAs
• On bounded-probability operators and C\(_ =\)P
• Error-bounded probabilistic computations between MA and AM
• Strong self-reducibility precludes strong immunity
• Probabilistic complexity classes and lowness
• Immunity and Simplicity for Exact Counting and Other Counting Classes

This page was built for publication: On closure properties of bounded two-sided error complexity classes

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