Simulating probabilistic by deterministic algebraic computation trees

Abstract

A probabilistic algebraic computation tree (probabilistic ACT) which recognizes L ⊂ Rn in expected time T, and which gives the wrong answer with probability ≤ ε{lunate} < 1 2, can be simulated by a deterministic ACT in O(T2n) steps. The same result holds for linear search algorithms (LSAs). The result for ACTs establishes a weaker version of results previously shown by the author for LSAs, namely that LSAs can only be slightly sped up by their nondeterministic versions. This paper shows that ACTs can only be slightly sped up by their probabilistic versions. The result for LSAs solves a problem posed by Snir (1983). He found an example where probabilistic LSAs are faster than deterministic ones and asked how large this gap can be. © 1985.