Probabilistic complexity classes and lowness

DOI10.1016/0022-0000(89)90020-2zbMath0688.68045OpenAlexW1999384241MaRDI QIDQ1263979

Uwe Schoening

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

zbMATH Keywords

probabilistic classesprobability amplificationquantifier simulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

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