Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
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.
Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
Lixi Zhou, Jiaqing Chen, et al.
VLDB
Pradip Bose
VTS 1998
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021