Probabilistic complexity classes and lowness
From MaRDI portal
Publication:1263979
DOI10.1016/0022-0000(89)90020-2zbMath0688.68045MaRDI QIDQ1263979
Publication date: 1989
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(89)90020-2
68Q25: Analysis of algorithms and problem complexity
Related Items
Restrictive Acceptance Suffices for Equivalence Problems, On closure properties of bounded two-sided error complexity classes, ON HIGHER ARTHUR-MERLIN CLASSES, On pseudorandomness and resource-bounded measure, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, Improving known solutions is hard, Autoreducibility, mitoticity, and immunity, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, On sparse hard sets for counting classes, Boolean operations, joins, and the extended low hierarchy, On collapsing the polynomial-time hierarchy, Some connections between bounded query classes and non-uniform complexity., New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, Error-bounded probabilistic computations between MA and AM, A note on the circuit complexity of PP, On Toda’s Theorem in Structural Communication Complexity, On lower bounds of the closeness between complexity classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some consequences of non-uniform conditions on uniform classes
- On small generators
- BPP and the polynomial hierarchy
- A low and a high hierarchy within NP
- Strong nondeterministic polynomial-time reducibilities
- Random generation of combinatorial structures from a uniform distribution
- On helping by robust oracle machines
- Does co-NP have short interactive proofs ?
- Graph isomorphism is in the low hierarchy
- Some observations on the probabilistic algorithms and NP-hard problems
- Reductions on NP and p-selective sets
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Robustness of probabilistic computational complexity classes under definitional perturbations
- On Circuit-Size Complexity and the Low Hierarchy in NP
- On Approximation Algorithms for # P
- Sparse Sets, Lowness and Highness
- On Tally Relativizations of $BP$-Complexity Classes
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Computational Complexity of Probabilistic Turing Machines
- The knowledge complexity of interactive proof-systems
- A decisive characterization of BPP
- Generalized lowness and highness and probabilistic complexity classes
