Amplification of slight probabilistic advantage at absolutely no cost in space
Nondeterministic Turing accepters can be viewed as probabilistic accepters with errors that are one-sided but not significantly bounded. We show how to transform such a machine to an equivalent one that does have a good error bound, at absolutely no cost in either space usage or storage-tape alphabet size. We have exactly the same space-bound complexity classes and hierarchy for bounded-one-sided-error probabilistic computation that we have for nondeterministic computation. Similarly, we have the same number-of-heads complexity classes and hierarchy for bounded-one-sided-error probabilistic multihead finite automata as for nondeterministic ones. (C) 1999 Elsevier Science B.V. All rights reserved.
computational complexity space complexity probabilistic turing machine nondeterministic turing machine multihead finite automaton