On closure properties of bounded two-sided error complexity classes

DOI10.1007/BF01303057zbMATH Open0827.68046MaRDI QIDQ4835865FDOQ4835865

Authors: James S. Royer, Kenneth W. Regan 

Publication date: 13 December 1995

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

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)

zbMATH Keywords

complexity class

Mathematics Subject Classification ID

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

Cites Work

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

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)