Error-bounded probabilistic computations between MA and AM
From MaRDI portal
Publication:2507698
DOI10.1016/j.jcss.2006.05.001zbMath1100.68023OpenAlexW2050981589MaRDI QIDQ2507698
Elmar Böhler, Daniel Meister, Christian Glaßer
Publication date: 5 October 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2006.05.001
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
The Untold Story of $$\mathsf {SBP}$$ ⋮ The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Unnamed Item ⋮ Rectangles Are Nonnegative Juntas ⋮ Unnamed Item ⋮ On the probabilistic closure of the loose unambiguous hierarchy ⋮ The complexity of estimating min-entropy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- BPP and the polynomial hierarchy
- A note on complete problems for complexity classes
- Does co-NP have short interactive proofs ?
- Complexity classes without machines: on complete languages for UP
- Relativized Arthur-Merlin versus Merlin-Arthur games
- Are there interactive protocols for co-NP languages?
- Some observations on the probabilistic algorithms and NP-hard problems
- A comparison of polynomial time reducibilities
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- A second step toward the polynomial hierarchy
- Universal classes of hash functions
- Probabilistic complexity classes and lowness
- Gap-definable counting classes
- Perceptrons, PP, and the polynomial hierarchy
- Computation times of NP sets of different densities
- An oracle builder's toolkit
- PP-lowness and a simple definition of AWPP
- Relativized worlds with an infinite hierarchy
- Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
- PRIMES is in P
- PP is closed under intersection
- Complexity limitations on quantum computation
- A complexity theory for feasible closure properties
- Automata Studies. (AM-34)
- Robustness of probabilistic computational complexity classes under definitional perturbations
- Bounded Query Classes
- The difference and truth-table hierarchies for NP
- A Fast Monte-Carlo Test for Primality
- Computational Complexity of Probabilistic Turing Machines
- BANISHING ROBUST TURING COMPLETENESS
- Threshold Computation and Cryptographic Security
- Quantum Complexity Theory
- ON THE DIFFERENCE BETWEEN CONSECUTIVE PRIMES
This page was built for publication: Error-bounded probabilistic computations between MA and AM