On the power of randomized multicounter machines

DOI10.1016/j.tcs.2004.09.015zbMath1078.68037MaRDI QIDQ1763706

Juraj Hromkovič, Georg Schnitger

Publication date: 22 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.09.015

zbMATH Keywords

Nondeterminism; Randomness; Determinism; Multicounter machines; Problem complexity

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Related Items

SIMULATIONS BY TIME-BOUNDED COUNTER MACHINES, Simulations by Time-Bounded Counter Machines

Cites Work

• Communication complexity
• Projections of languages recognizable by probabilistic and alternating finite multitape automata
• On the distributional complexity of disjointness
• Properties of probabilistic pushdown automata
• Exact lower time bounds for computing Boolean functions on CREW PRAMs
• Amplification of slight probabilistic advantage at absolutely no cost in space
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• The Probabilistic Communication Complexity of Set Intersection
• Computational Complexity of Probabilistic Turing Machines
• Communication Complexity
• Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item