NONDETERMINISTIC VERSUS PROBABILISTIC LINEAR SEARCH ALGORITHMS.

Abstract

The 'component counting lower bound' known for deterministic linear search algorithms (LSAs) also holds for their probabilistic versions (PLSAs) for many problems, even if two-sided error is allowed, and if one does not charge for probabilistic choice. This implies lower bounds on PLSAs for, e. g. , the element distinctness problem (n log n) or the knapsack problem (n+ZZThese results yield the first separations between probabilistic and nondeterministic LSAs, because the above problems are nondeterministically much easier. Previous lower bounds for PLSAs either only worked for one-sided error on the side where the problems are hard even nondeterministically or only for probabilistic comparison trees.