On the power of randomized multicounter machines

DOI10.1016/j.tcs.2004.09.015zbMath1078.68037OpenAlexW2078378888MaRDI 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

NondeterminismRandomnessDeterminismMulticounter machinesProblem complexity

Mathematics Subject Classification ID

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

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: On the power of randomized multicounter machines