Error-bounded probabilistic computations between MA and AM

DOI10.1016/J.JCSS.2006.05.001MaRDI QIDQ2507698zbMATH OpenOpenAlexFDO

Authors Elmar Böhler, Christian Glaßer, Daniel Meister

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

zbMATH Keywords

promise problemsprobabilistic machinescounting classesArthur-Merlin classes

Mathematics Subject Classification ID

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

Recommendations

• Mathematical Foundations of Computer Science 2003
• Probabilistic complexity classes and lowness
• On closure properties of bounded two-sided error complexity classes
• On bounded-probability operators and C\(_ =\)P
• scientific article; zbMATH DE number 3943795

Cites work

• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 1500532 (Why is no real title available?)
• A Fast Monte-Carlo Test for Primality
• A comparison of polynomial time reducibilities
• A complexity theory for feasible closure properties
• A note on complete problems for complexity classes
• A second step toward the polynomial hierarchy
• An oracle builder's toolkit
• Are there interactive protocols for co-NP languages?
• Automata Studies. (AM-34)
• BANISHING ROBUST TURING COMPLETENESS
• BPP and the polynomial hierarchy
• Bounded Query Classes
• Complete sets and the polynomial-time hierarchy
• Complexity classes without machines: on complete languages for UP
• Complexity limitations on quantum computation
• Computation times of NP sets of different densities
• Computational Complexity of Probabilistic Turing Machines
• Does co-NP have short interactive proofs ?
• Gap-definable counting classes
• ON THE DIFFERENCE BETWEEN CONSECUTIVE PRIMES
• PP is closed under intersection
• PP-lowness and a simple definition of AWPP
• PRIMES is in P
• Perceptrons, PP, and the polynomial hierarchy
• Probabilistic complexity classes and lowness
• Quantum Complexity Theory
• Relativized Arthur-Merlin versus Merlin-Arthur games
• Relativized separation of EQP from \(\text{P}^{\text{NP}}\)
• Relativized worlds with an infinite hierarchy
• Robustness of probabilistic computational complexity classes under definitional perturbations
• Some observations on the probabilistic algorithms and NP-hard problems
• The difference and truth-table hierarchies for NP
• The polynomial-time hierarchy
• Threshold Computation and Cryptographic Security
• Universal classes of hash functions

Cited in

(12)

• The layer complexity of Arthur-Merlin-like communication
• The complexity of estimating min-entropy
• Mathematical Foundations of Computer Science 2003
• Quantum lower bounds for approximate counting via Laurent polynomials
• On the probabilistic closure of the loose unambiguous hierarchy
• Rectangles are nonnegative juntas
• scientific article; zbMATH DE number 1304314 (Why is no real title available?)
• The landscape of communication complexity classes
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Zero-information protocols and unambiguity in Arthur-Merlin communication
• The Untold Story of $$\mathsf {SBP}$$
• Resource Bounded Frequency Computations with Three Errors

This page was built for publication: Error-bounded probabilistic computations between MA and AM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2507698)