Probabilistic complexity classes and lowness
From MaRDI portal
Publication:1263979
DOI10.1016/0022-0000(89)90020-2zbMath0688.68045OpenAlexW1999384241MaRDI 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
Related Items (27)
New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ On collapsing the polynomial-time hierarchy ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Uniform proofs of ACC representations ⋮ On closure properties of bounded two-sided error complexity classes ⋮ Autoreducibility, mitoticity, and immunity ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ On lower bounds of the closeness between complexity classes ⋮ The join can lower complexity ⋮ On the complexity of matroid isomorphism problem ⋮ On a theorem of Razborov ⋮ Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem ⋮ A complex analogue of Toda's theorem ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ ON HIGHER ARTHUR-MERLIN CLASSES ⋮ Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P ⋮ Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy ⋮ Improving known solutions is hard ⋮ On sparse hard sets for counting classes ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ On pseudorandomness and resource-bounded measure ⋮ On Toda’s Theorem in Structural Communication Complexity ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Boolean operations, joins, and the extended low hierarchy ⋮ A note on the circuit complexity of PP ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ On the probabilistic closure of the loose unambiguous hierarchy
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
This page was built for publication: Probabilistic complexity classes and lowness
