Amplification of slight probabilistic advantage at absolutely no cost in space

DOI10.1016/S0020-0190(99)00129-5zbMath0999.68067OpenAlexW2087974580MaRDI QIDQ1607005

Ioan I. Macarie, Joel I. Seiferas

Publication date: 25 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(99)00129-5

zbMATH Keywords

nondeterministic Turing acceptors

Mathematics Subject Classification ID

Related Items (5)

Infinite vs. finite size-bounded randomized computations ⋮ On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata ⋮ Size complexity of rotating and sweeping automata ⋮ On the power of randomized multicounter machines ⋮ Size Complexity of Two-Way Finite Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Multihead two-way probabilistic finite automata
• Space-bounded hierarchies and probabilistic computations
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• Relating refined space complexity classes
• Characterization of realizable space complexities
• On non-determinacy in simple computing devices
• A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
• Computational Complexity of Probabilistic Turing Machines
• Some Results on Tape-Bounded Turing Machines

This page was built for publication: Amplification of slight probabilistic advantage at absolutely no cost in space