Amplification of Slight Probabilistic Advantage at Absolutely No Cost in Space

. Nondeterministic Turing acceptors can be viewed as probabilistic acceptors with errors that are one-sided but not significantly bounded. In his seminal work on resource-bounded probabilistic Turing machines [Gi77], Gill showed how to transform such a machine to one that does have a good error bound, at only modest cost in space usage. We describe a simpler transformation that incurs absolutely no cost in space usage. If we change each probabilistic transition to a nondeterministic one, then we get a space-preserving transformation in the opposite direction as well, assuming the definitions are right. Thus the complexity classes are exactly the same, and we have the same space-bound hierarchy for bounded-one-sided-error probabilistic computation that we have for nondeterministic computation. Similarly, we have the same numberof -heads complexity classes and hierarchy for bounded-one-sided-error probabilistic multihead finite automata as for nondeterministic ones. 1. Introduction Wh..